[RESOLVED] [Help] F9 - AS3 - Map Range

[Battlespace]

Using F9 and AS3... determining range within a map of uneven borders (non-hex, non-square)...

Download FLA here: range.zip

The link above contains the fla and xml files used to demonstrate a problem I'm having in a game. The file was too big for the forum attachment restrictions. This is not the actual game file or graphics...



As you can see in the image, section 4 is selected in green using the numeric stepper. This represents the starting point and all sections within range (based on a second numeric stepper) around it are in white. The section labels and borders are defined in the xml file. Some sections could have 2 borders... some 6.

The problem is I can't get anything greater than a range of 1 to work. I've tried calling the function recursively but I get a stack overflow... just not getting it right somewhere. I have removed all of my attempts and just let the code as-is with range ignored.

An example using the image above... if I was to change the range to 2 and leave the starting point at section 4... sections 3, 6, 8 would also turn white (in addition to what is seen above)... because they are 2 sections within range of 4.

Thanks in advance for any help...

Regards,
Brent

[rachil0]

This is a standard graph problem.
http://en.wikipedia.org/wiki/Graph_theory
In your case, the graph vertices are the regions, and graph edges are the connections between regions - the shared borders.

Solve it using breadth first search.
http://en.wikipedia.org/wiki/Breadth_first_search

Cormen et. al is a peerless reference for all kinds of standard computer science algorithms, and includes several chapters on graph-theoretic problems. It is technical reading however.
http://www.fetchbook.info/fwd_descri...262032933.html

Check out the wiki-links and see if you can make heads & tails out of it. I can post more details later - but busy atm.

EDIT: Your recursive idea should also work - it should behave like depth-first search (with limited depth, set by the range box). A possible reason that your function doesn't halt is that you are forgetting to mark vertices as "already visited" - so your algorithm could easy loop forever on a simple graph of 2 nodes and 1 edge (each subcall sees one unvisited neighbor and happily recurses indefinitely).

[Battlespace]

Thanks for the links to the information... and for the tip on the recursive issue. I'm going to give it a try this week. Once I have a solution or more questions, I will post here.

Thanks again,
Brent

[Battlespace]

I have uploaded a new version of the FLA at the same link in the first message above. There were a couple of errors in my original xml file as well.

I now have the recursive function working without an overflow error by using an array to store sections that have been visited. I can't figure out the best way to limit the recursive call based on the range value. The last function listed in the first frame (script label) is the recursive function.

I tried to prevent recursive calls depending on the range but it was not 100% accurate so I must still be doing something wrong.

I'm sure this is easy for someone that has done it before... any help would be appreciated.

Regards,
Brent

[rachil0]

Try to make sense of this - I've tried to imitate the recursive solution that you're trying for. Copy & paste into Main.as. Compile from command line.

// Compile me with:
// mxmlc Main.as
package 
  {	
  import flash.display.Sprite;
  import flash.text.TextField;
  
  public class Main extends Sprite 
    {      
    private var N_vertices : int;
    private var connections : Array;
    private var visitedYet : Array;
      
    public function Main() 
      {  
      // Define the graph. It has 10 vertices.
      N_vertices = 10;
      var n : int;
      // Allocating an "adjacency list" to represent the edges. It's an "array of arrays".
      connections = new Array;
      for (n = 0; n < N_vertices; n++)
        connections[n] = new Array;
      // Making connections between vertices - follows the figure you provided.
      // vertex 1, it's connected to vertices 2 and 4.
      connect(1,2); connect(1,4);
      // vertex 2, connected to 1,3,4,5,6
      connect(2,1); connect(2,3); connect(2,4); connect(2,5); connect(2,6);
      connect(3,2); connect(3,6);
      connect(4,2); connect(4,1); connect(4,5); connect(4,7);
      connect(5,2); connect(5,4); connect(5,6); connect(5,7); connect(5,8); connect(5,9);
      connect(6,3); connect(6,5); connect(6,2); connect(6,10); connect(6,9);
      connect(7,4); connect(7,5); connect(7,8);
      connect(8,5); connect(8,7); connect(8,9);
      connect(9,5); connect(9,6); connect(9,8); connect(9,10);
      connect(10,6); connect(10,9);
      // All done - hope i didn't miss any (but it's possible).
      
      // Mark all vertices as unvisited.
      visitedYet = new Array;
      for (n = 0; n < N_vertices; n++)
        visitedYet[n] = false;
      // Depth-first search, with maximum depth.
      var start : int = 10;
      var depth : int = 2;
      //   *******                 node to start from "Start" in your app.
      //            *****          how deep to go. "Range" in your app.      
      dfs (start-1, depth);
      
      // Report which vertices were visited. Slapped into a text field.
      var s : String = "Vertices that are at most " + depth + " hops away from " + start + ".\n";
      for (n = 0; n < N_vertices; n++)
        if (visitedYet[n])
          s = s + (n+1) + " ";
      
      var cout : TextField = new TextField();
      cout.textColor = 0xFFFF00FF;
      cout.x = 0;
      cout.y = 0;
      cout.width = 800;
      cout.height = 100;
      addChild(cout);
      
      cout.text = s;
      }
    
    private function dfs (root : int, depth : int) : void
      {
      // Tail recusion - if we've gone as deep as we're permitted, stop searching.
      if (depth < 0)
        return;
      else
        {
        // Visit the root vertex.
        visitedYet[root] = true;
        // Visit all neighbors of root. We decrement the maximum depth 
        // we're allowed to look from here on out, because we used up 
        // 1 depth-unit getting to root from its predecessor.
        for (var i : int = 0; i < connections[root].length; i++)
          dfs(connections[root][i], depth-1);
        }
      }
    
    private function connect(i : int, j : int) : void
      {
      // Why -1's? I start counting at zero, but the figure starts counting at 1.
      // I recommend that you start counting from zero from now on.
      connections[i-1].push(j-1);
      }
    }
  }

The basic key to the recursion:
The set of vertices which are range R away from vertex V.
=
The set of vertices which are range R-1 away from any neighbor of V.

And the tail:
The set of vertices which are range 0 away from vertex V
=
just vertex V.

But like I said - the problem is more elegantly solved using BFS. This visits each vertex multiple times, BFS will just visit each one once.

EDIT: Removed out-of-date comment about starting from vertex 4 - we're starting at 10.

[Battlespace]

I really appreciate the time it took for you to help... I will study and learn from it.

I tested your code and it works great... I will work on implementing this logic into my existing project.

Thank you,
Brent

[rachil0]

Here is a breadth-first-search solution to the problem. I strongly recommend you use it instead of the recursive DFS solution. On large datasets and deep ranges, DFS will grind to a halt (as it is currently coded, it's running time grows exponentially with respect to depth). The BFS solution will scale linearly with respect to (number of edges + number of vertices).

Please report bugs

// Compile me with:
// mxmlc Main.as
package 
  {	
  import flash.display.Sprite;
  import flash.text.TextField;
  
  public class Main extends Sprite 
    {      
    private var N_vertices : int;
    private var connections : Array;
    private var depthToVertex : Array;
    private static const UNVISITED : int = -1;
    
    public function Main() 
      {  
      // Define the graph. It has 10 vertices.
      N_vertices = 10;
      var n : int;
      // Allocating an "adjacency list" to represent the edges. It's an "array of arrays".
      connections = new Array;
      for (n = 0; n < N_vertices; n++)
        connections[n] = new Array;
      // Making connections between vertices - follows the figure you provided.
      // vertex 1, it's connected to vertices 2 and 4.
      connect(1,2); connect(1,4);
      // vertex 2, connected to 1,3,4,5,6
      connect(2,1); connect(2,3); connect(2,4); connect(2,5); connect(2,6);
      connect(3,2); connect(3,6);
      connect(4,2); connect(4,1); connect(4,5); connect(4,7);
      connect(5,2); connect(5,4); connect(5,6); connect(5,7); connect(5,8); connect(5,9);
      connect(6,3); connect(6,5); connect(6,2); connect(6,10); connect(6,9);
      connect(7,4); connect(7,5); connect(7,8);
      connect(8,5); connect(8,7); connect(8,9);
      connect(9,5); connect(9,6); connect(9,8); connect(9,10);
      connect(10,6); connect(10,9);
      // All done - hope i didn't miss any (but it's possible).
      
      
      // Mark all vertices as unvisited.
      depthToVertex = new Array;
      for (n = 0; n < N_vertices; n++)
        depthToVertex[n] = UNVISITED;
      
      var start : int = 10;
      bfs (start-1);
      
      // Report the depths of all vertices. Slapped into a text field.
      var s : String = "Depths of all vertices, measured from vertex " + start + "....\n";
      for (n = 0; n < N_vertices; n=n+1)
        s = s + "Vertex " + (n+1) + ", depth = " + depthToVertex[n] + "\n";
      
      var cout : TextField = new TextField();
      cout.textColor = 0xFFFF00FF;
      cout.x = 0;
      cout.y = 0;
      cout.width = 800;
      cout.height = 300;
      addChild(cout);
      
      cout.text = s;
      }
    
    private function bfs (root : int) : void
      {
      // FIFO array of vertices yet to be visited.
      var vertexQueue : Array = new Array;
      // Mark the root (start) vertex at depth 0.
      vertexQueue.push(root);
      depthToVertex[root] = 0;
      
      while(vertexQueue.length > 0)
        {
        // Pop a vertex off the front of the list.
        var v : int = vertexQueue.shift();
        var v_depth : int = depthToVertex[v];
        // Look at all of v's neighbors. If they are still unvisited,
        // then mark their depth as v_depth+1. Then enqueue them.
        for (var i : int = 0; i < connections[v].length; i++)
          {
          var v_neighbor : int = connections[v][i];
          if ( depthToVertex [v_neighbor] == UNVISITED )
            {
            depthToVertex [ v_neighbor ] = v_depth + 1;
            vertexQueue.push(v_neighbor);
            }
          }
        }
      }
    
    
    
    private function connect(i : int, j : int) : void
      {
      // Why -1's? I start counting at zero, but the figure starts counting at 1.
      // I recommend that you start counting from zero from now on.
      connections[i-1].push(j-1);
      }
    }
  }

[Battlespace]

Thanks for posting this alternate solution. I'll try it when I get home this afternoon. If I have any questions, I'll post here... at first glance I don't see how the code knows the range ("depth")... I'll take a stab at it and see if it makes sense after I run it.

My maps for this game are at the largest 50 sections and the highest range is maybe 10 for a unit. It will be used to highlight which sections a unit may move to based on their maximum range so the faster the better...

Thanks again,
Brent

[Battlespace]

Hello,

I tried this new code and it works great... I see how the depth works in this version now.

Thanks again for your help,
Brent