I am using Irrlicht 3d engine and going to add AI to my project.
I still don't know how to do with that, i am finding relative materials.
If anyone know about this, please give me some advices! Thanks a lot!
2
how to integrate A* pathfinding algorithm with 3d engine?
Started by michael520, Nov 21 2005 07:00 AM
5 replies to this topic
#2
-
- Members
-
- 413 posts
Senior Member
Posted 21 November 2005 - 10:20 AM
Theres a couple of really good articles on path finding in the first Game Programming Gems book, well worth getting.
Basically, what you do with A* is find the least expensive route from one node to another node. "Expensive" can mean just about anything, and "node" can also be just about anything. In the most common case of pathfinding, a node is usually a cell in a 2d grid, and the cost is distance. You provide A* with the node, and a way to get to each nodes neighbours, as well as two methods for cost calculation: the first calculates the cost for moving to a specific node from the start node (this we can usually calculate accurately, with a 2d grid for nodes it's very straightforward) and the second one calculates the cost for moving to the end node from a specific node (this is usually an estimate, as we probably don't know for sure until we've found the path).
To extend this to a 3D world, all we need to do is use a suitable type for our nodes, along with functions to get a nodes neighbours and calculate and estimate the costs.
What type of nodes we use can have a huge impact on performance. The most efficient type of nodes is probably if you manually create a pathfinding network for each level, by placing and connecting nodes. A quite inefficient way would be to use a 3d grid (like a cube build up of many little cubes, each a node for the pathfinding, with some marked as not walkable), but this could be automatically generated. Other techniques involve using the existing polygons of, say, the floors, as pathfinding nodes, but this makes the cost estimate/calculate methods slightly more complicated.
There's lots of different ways to do 3d pathfinding with A*, but what they all have in common is that they all have the nodes, with neighbours, and cost calculate/estimate functions.
An interesting thing to note, is that A* can be used for all sorts of problem solving besides path finding, where you can break down the problem into nodes and write good enough cost calculate/estimate functions.
Basically, what you do with A* is find the least expensive route from one node to another node. "Expensive" can mean just about anything, and "node" can also be just about anything. In the most common case of pathfinding, a node is usually a cell in a 2d grid, and the cost is distance. You provide A* with the node, and a way to get to each nodes neighbours, as well as two methods for cost calculation: the first calculates the cost for moving to a specific node from the start node (this we can usually calculate accurately, with a 2d grid for nodes it's very straightforward) and the second one calculates the cost for moving to the end node from a specific node (this is usually an estimate, as we probably don't know for sure until we've found the path).
To extend this to a 3D world, all we need to do is use a suitable type for our nodes, along with functions to get a nodes neighbours and calculate and estimate the costs.
What type of nodes we use can have a huge impact on performance. The most efficient type of nodes is probably if you manually create a pathfinding network for each level, by placing and connecting nodes. A quite inefficient way would be to use a 3d grid (like a cube build up of many little cubes, each a node for the pathfinding, with some marked as not walkable), but this could be automatically generated. Other techniques involve using the existing polygons of, say, the floors, as pathfinding nodes, but this makes the cost estimate/calculate methods slightly more complicated.
There's lots of different ways to do 3d pathfinding with A*, but what they all have in common is that they all have the nodes, with neighbours, and cost calculate/estimate functions.
An interesting thing to note, is that A* can be used for all sorts of problem solving besides path finding, where you can break down the problem into nodes and write good enough cost calculate/estimate functions.
#3
-
- Members
-
- 12 posts
New Member
Posted 06 December 2005 - 02:31 AM
Oh Mattias, thank very much!
My 3d simulation project must have a path-finding algorithm to make objects go the right and shortest way. Or could I just provide some polygon-paths for the terrain?
All I have to do is hard-hard working to search and think~~~~
Thanks for giving me more advices...
My 3d simulation project must have a path-finding algorithm to make objects go the right and shortest way. Or could I just provide some polygon-paths for the terrain?
All I have to do is hard-hard working to search and think~~~~
Thanks for giving me more advices...
#4
-
- Members
-
- 1239 posts
Senior Member
Posted 07 December 2005 - 06:48 AM
You can split the terrain up into possible paths, but you really need an algorithm to find a route for players to move over - try A*.
#5
-
- Members
-
- 17 posts
New Member
Posted 20 December 2005 - 09:43 PM
What you are looking for is usually called waypoints.
How you set them depends on the style of map. On a terrain, you could as simply just set a point in the center of each tile on a quadtree. In a map like a quake game, your mappers would most likely place them in strategic points to optimize the performance of searching. Typically, you would break the pathing down in some way in a real-time game, from smaller searches. In an RTS, for instance, paths can change dynamically (buildings get put down on the map) and recalculating the A* all the time is expensive. So you break it down into smaller subsearches to get to the final goal. Then there are other tricks, to make it smoother, or more realistic. It is annoying if the robot follows the path, well... like a robot...
Game Gems had a ton of articles about this year's ago, you might want to go to the bookstore and (ahem) get a coffee and read the chapters. I think it was book's 1 and 2.
How you set them depends on the style of map. On a terrain, you could as simply just set a point in the center of each tile on a quadtree. In a map like a quake game, your mappers would most likely place them in strategic points to optimize the performance of searching. Typically, you would break the pathing down in some way in a real-time game, from smaller searches. In an RTS, for instance, paths can change dynamically (buildings get put down on the map) and recalculating the A* all the time is expensive. So you break it down into smaller subsearches to get to the final goal. Then there are other tricks, to make it smoother, or more realistic. It is annoying if the robot follows the path, well... like a robot...
Game Gems had a ton of articles about this year's ago, you might want to go to the bookstore and (ahem) get a coffee and read the chapters. I think it was book's 1 and 2.
#6
-
- Members
-
- 12 posts
New Member
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users
