3D game demonstrating A* algorithm?

#1 Hi there, I had this same problem a few weeks ago. I understould the algorithm perfectly (which it seems you do too) but had no idea how to implement it. I'll explain this really simply, you probably know alot of the stuff I'm going to mention, but I'd rather say it all than cut out too much for simplicity's sake. I'll do my best to explain it, but I'm not the best at describing processes like this. And I tend to make them seem alot harder to do :P so bear with me.

This is what I'm doing to make an A* grid that will generate itself upon a given consoleFunction() and save it to a file with the same name heading as the mission file. I'm not done with it yet however, so I won't have much completed code to show you if it's needed. There are many other ways to do it, and I may have done a few things wrong, or not as efficiently as I could of, but it gets the job done.

The first steps of it would be to edit the C++ source of the engine to add nodes for A* and pathfinding functions. If you are unable to do this, it can all be done in script, it just executes slower and is more resource heavy. First thing I did was looked at several resources of people implementing A* into C++. Ramen Sama did a great job of this.

Next it converting that into code useable for TGE.

First, we need to get the getTerrainHeight() console function under terrainData.h Copy that function and edit it to be an engine function called terrainHeight().

Instead of using pixels like other versions of A*, you would make nodes. This can be done simply through making the node class in the source, give it a value of it's XYZ position ingame, it's XY value of it through the current graph (e.g. if you have nodes spread 5m apart, the XY of the 10th node in the first row is (50, 0) but along the grid it's (10, 1).) Since you don't have large areas being just "walkable" or "unwalkable" like you would in a pixelated node version, remove each nodes "unwalkable" value. There are 2 ways to do this. If you're going to manually place nodes this may not be necessary, as you can just avoid creating or linking nodes that are unreachable, though this messes up the algorithm being able to estimate adjacent nodes based on it's grid coordinates.

1) This is simpler to set up, but the data it stores becomes redundant as it will keep track of each path twice (once for A to B, then from B to A, when we really only need 1 way. Make it an array of 8 values. Whether or not the path from the currentNode to an adjacent node is clear. Now continure until we get to the checkPathing phase. checkPathing:
Now do the 2 loops again, under the 2nd loop, get the i and i2 variable and find the node matching the same grid Coordinates. castRay to each adjacent node (nodes with gridCoords (i+1, i2+1) & (i, i2+1) & (i-1,i2+1) & etc...) if the castRay reaches the adjacent node, set the walkable from the current node to that one as adjacent. Then also set the adjacent node to the current node as walkable. You see? We access directly from the nodes here, so we can't just look at the other node to see if we can walk here without dividing the grid into spaces seperating every other row. This however leaves the seperated rows with empty walkable variables, the 2nd method creates a new array and is more efficient for that design.
2) The first way is more complex but handles memory more efficiently. I'm not sure the exact implementation (more complex, eh :p) but you create a variable with 2 arrays for the X,Y of 1/2 the gridDim (so every other row/column is effected) and 2 more for 3 values (4 layer matrix total). The last 2 arrays are the modifier to find the adjacent node (what you add to the gridCoords to find it) When you need to check a path, you get the X and Y of the node you start from, divide by 2 and round down. This will always give you column/row that has been stored in the arrays. Get the difference between the currNode X,Y and the adjNode along the gridCoords. Add 1 to this (since you can't have -1 as an array place, we make it 0.) Then you check whether that variable, with matrix filled, is true of false. That's your walkability.
to checkPathing:
you would loop 1/2 of the gridDim twice (X and Y loops) multiply the value of the loop by 2 (this is your gridCoord) cast a ray to the adjacent node, and set walkable[i][i2][a+1][b+1] a & b are equal yo what you added/subtracted to modify the current node into the adjacent node.

If you're going to give any nodes values to add to the path G value, create that in here too (like maybe nodes on sand cost double.)

Now create a console function that takes in the inputs, gridDimension, gridSpacing, and gridStart. gridDimension is how many nodes to make on each axis (gridDimension = 10 means you have 100 nodes total, 10x10) gridSpacing is how many units apart to place each node from the adjacent ones (not the diagonal) gridStart will be what location ingame the topleft corner of the grid is placed at.

Start by seperating the gridStart into an X an Y value. Loop (i=0; i++; i = gridDimension), and inside that loop, place another loop with the same stats just different variables (i2=0; i2++; i2 = gridDimension), . The first loop is for the X, second for the Y. What you're doing here is (in the 2nd loop) making each Y column of nodes, and once that column is finished (in the 1st loop) start over, but gridDim to the X. Under the 2nd loop, multiply i and i2 x gridDimension. This is how many units form the starting node you are. Add these with the startNode X and Y. Make this a Point2F and find the terrainHeight() this. Convert these to a Point3F and make the terrainHeight() the Z. Now add the node to the scene based on the Point3F.

see the checkPathing() part of whichever walkabilty store you chose.

Now all the data is established and you should be able to run a normal A* code, with the variable types just modified to fit TGE.

Based on all these values, save them to a .cs file (I'm still working on this. You should be able to demonstrate the A* pathfinding functions still however, because the variables aside from being saved to a .cs are still running in the game's memory. Just every time you demonstrate this, you would need to create/compile the nodes as we just have in this code. Otherwise, you would only need to execute this just once per map and then load it on missionStart.) Then another function to load node data from a .cs file that the path is given in the function, which again I'm still doing. Maybe extra credit to anyone who could do the saving/loading :p

I hope this helps you out.

#2 For my project all navigation will be done in 2d, even in a 3d environment. basically i will create a 2d representation of navigatable areas. and run the pathfinding code to go to the area needed.

i wrote a blog awhile back with some example code.

www.garagegames.com/blogs/11127/14049

May be of interest. what i like about it is the fact i got it to adapt to multisize objects navigating on the grid.

::edit:: wow, i guess i should have completely read the previous post, since it mentioned me and my blog. oh well. Sorta made my post pointless :p

#3 Haha, it's all good Ramen. By the way, that resource I linked helped me with A* so much, it'd still all be psuedo-code without ya, thanks for putting that up.