We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
Page Index Toggle Pages: 1
AStar (Read 531 times)
AStar
Jul 4th, 2006, 8:02pm
 
TomC has an AStar example up that I've been looking at with developing my library. The object orientated approach seems a little more straight forward and less buggy than my method but I didn't quite like the Pandora's box approach with the Nodes (within nodes, within nodes, etc.). So I set about integrating my code and his (so it would operate from 4 directions upto a 26 directional cube - by means of a quick algorithm, no 26 conditions this time). I also couldn't use his "walkable" method - otherwise I wouldn't be able to do things like snake.

But I really don't get what is going on with Tom's use of G. I want to use it as a terrain modifier. It's important to give users that option. This is the section giving me trouble.
Code:

// otherwise, loop through neighbours
Iterator iter = current.neighbours.iterator();
while(iter.hasNext()) {
Node adjacent = (Node)iter.next();
if (adjacent.walkable && !closed.contains(adjacent)) {
if (!open.contains(adjacent)) {
open.add(adjacent);
adjacent.parent = current;
adjacent.setF(finish);
}
else {
// if this is a better way to get there than last time we looked at it
if (adjacent.g > current.g + current.location.dist(adjacent.location)) {
adjacent.parent = current;
adjacent.setF(finish);
}
}
}
}

Without the else block this code performs BFS (Best First Search). I like having that option - a stupid search could be interesting. But I need to figure out the else block for my code.
Code:

for(int j = 0; j < current.child.length; j++){
//instead of stripping walkables, just check terrain is set above 0
if(n[current.child[j]].g >= 0 && !closed.contains(n[current.child[j]])){
if(!open.contains(n[current.child[j]])){
open.add(n[current.child[j]]);
n[current.child[j]].parent = current.id;
n[current.child[j]].setF(finish, fast);
}
//removing this else makes the search imitate bfs
else{
//ergo must be on open? - hence the bfs
if(n[current.child[j]].p.dist( > current. //arrghh?!?!?
n[current.child[j]].parent = current.id;
n[current.child[j]].setF(finish, fast);
}
}
}

The trouble in translation is Tom's Node class:
Code:

public void setG() {
g = parent.g + location.dist(parent.location);
}

If someone can assure me that Tom's Pandora Nodes won't eat up memory then I'll do a direct transcript and fit in the extra stuff like being able to search in 3 dimensions, wrapped environments, corners or no, BFS, etc. I could always add the terrain modifier as a separate value inside the Nodes.

Preferably I'd like to understand what is going on in Tom's else block and with his setting of G. I'd rather not be a copy/paste monkey.
Re: AStar
Reply #1 - Jul 5th, 2006, 11:10am
 
Can you explain what your worries are with memory?

The neighbours list just contains references to the Node objects.  Those should only take up 4 bytes each I think (need to look it up in the java spec) - that's tiny!

So for a 50x50 grid, with 8-way connectivity, the maximum space the neighbours lists can take up is 50*50*8*4bytes =~ 80KB... not a lot really in today's terms.  There is overhead for using Vectors (reserved space, and memory for the Vector object itself) which I suppose could blow up quickly.  Obviously the memory goes up with the square of the grid size, so 100x100 grid takes 4 times as much memory to store the neighbours.

Then remember that after I set up 8-way connectivity, I prune off all the impassable neighbours, so I only need to check things once.  You could leave them in so that walkableness could be dynamic (for your snakes for example).

Granted, there are more efficient ways to store a grid, but the main advantage with this is that it is easily generalised to any space... For example you might want to plot paths across an arbitrary mesh.  You just need to say what is connected to what, and how much it costs to move from there to here.

I'm not sure what your issue with G is, I'll have to read the tutorial again and see if I can explain my own code!

Re: AStar
Reply #2 - Jul 5th, 2006, 1:33pm
 
That's okay then, I'll just do a direct port of your example for now. It just looked a bit weird from an Integer head like me. I'm fighting the urge to cast everything into ints.

The G calculation you've used makes sense from a floats point of view, I was just having trouble casting it into ints and imagining the node within the node, connected to the node. Trying to unpick that knot in my head without having first tied it was a pickle. So I'll skip that for now and stick a sign in the middle saying //Tom's code. I'll add a terrain float to the Nodes to make them walkable or difficult and that should make a pathway stripper easier to make too.

The 26 directional connector I wish I'd thought of sooner:
Quote:


void connect(boolean corners, boolean wrap){
 n = new Node[wide * high * deep];
 for(int x = 0; x < wide; x++){
   for(int y = 0; y < high; y++){
     for(int z = 0; z < deep; z++){
       //storage for our child nodes
       Vector temp = new Vector();
       //off we go in 26 directions!
       for(int i = -1; i < 2; i++){
         for(int j = -1; j < 2; j++){
           for(int k = -1; k < 2; k++){
             //skip the center of the cube
             if(i == 0 && j == 0 && k == 0) continue;
             //skip corners?
             if(!corners && !((i == 0 && j == 0 && k != 0) || (i == 0 && j != 0 && k == 0) || (i != 0 && j == 0 && k == 0))) continue;
             //when wraping the environment you need to skip depth
             if(deep < 2 && k != 0) continue;
             int xd = x + i;
             int yd = y + j;
             int zd = z + k;
             if(wrap){
               if(xd < 0) xd = wide - 1;
               if(yd < 0) yd = high - 1;
               if(zd < 0) zd = deep - 1;
               if(xd > wide-1) xd = 0;
               if(yd > high-1) yd = 0;
               if(zd > deep-1) zd = 0;
             }
             //is the connector legal?
             if(xd < wide && xd > -1 && yd < high && yd > -1 && zd < deep && zd > -1){
               int childId = xd + (yd * wide) + (zd * wide * high);
               temp.add(new Integer(childId));
             }
           }
         }
       }
       //dump our connectors into the node
       int [] children = new int[temp.size()];
       for(int i = 0; i < temp.size(); i++){
         Integer getInt = (Integer)temp.get(i);
         children[i] = getInt.intValue();
       }
       int id = x + (y * wide) + (z * wide * high);
       n[id] = new Node(id, children, new Point(x, y, z));
     }
   }
 }
}


Page Index Toggle Pages: 1