Speed in relation to PathFinding
by Matt Sanders · in Torque Game Engine · 03/16/2005 (9:04 am) · 1 replies
I have a nice state machine backbone that I will be implementing along with A* path finding algorithms. I am really brainstorming right now on what method would be 1) easy to implement on multiple maps and 2) not very CPU intensive. Basically I had a few Ideas on how I would like to separate the world for the AI to use A*.
1) separating the world into a grid with triggers in an array like formation. I was wondering how CPU intensive this would be because I want a Way to be able to identify blocks that have objects, players or
buildings occupying them.
2) set up multiple nodes in a grid formation and ray cast from each one as the A* searches through the path
to identify if a player, building, or vehicle is near it.
3) find out some other way to separate the world into a grid to implement the A*.
:)
Again this is basically just brainstorming Ideas and I would really just like to get a few suggestions or pointers from people out there that have already implemented their own form of path finding in torque. Basically I understand the Concept of A* I just am hung up on how I should separate the game space.
Any help is more then appreciated.
1) separating the world into a grid with triggers in an array like formation. I was wondering how CPU intensive this would be because I want a Way to be able to identify blocks that have objects, players or
buildings occupying them.
2) set up multiple nodes in a grid formation and ray cast from each one as the A* searches through the path
to identify if a player, building, or vehicle is near it.
3) find out some other way to separate the world into a grid to implement the A*.
:)
Again this is basically just brainstorming Ideas and I would really just like to get a few suggestions or pointers from people out there that have already implemented their own form of path finding in torque. Basically I understand the Concept of A* I just am hung up on how I should separate the game space.
Any help is more then appreciated.
About the author
Associate Manoel Neto
Default Studio Name
Forget the grid layout. It just generates buttloads of extra nodes that aren't always needed. A* doesn't depend on the grid stuff. The only thing a grid provides is an easy way to find neighbor nodes.
Instead of having a grid with open/closed nodes, use arbitraly placed nodes, that are open by default (aka: the nodes are in physically acessible areas). Then you calculate the neighborhood information youself, and store it in each node.
To do that, you'll need to loop through all nodes, for each node, and check if those nodes are acessible. The accesibility requirements will determinate your map layout. Start by performing line of sight tests to see if the target node is visible, and if so, add it to the neighbor list and store the distance to that node as the cost.
After you do that, each node will know the nodes one can acess from it, and how much it costs to travel to that node. Then you do your A* based on that information.
You can then refine your neighborhood calculation by filtering out nodes that are roughly in the same line, or checking height differences between the nodes, and so on.