I need to generate useful data for pathfinding purposes, and store it, when the input is a height map. The map itself is 2048^2 in dimensions, so I would need to store the data in a quadtree, and I also need to store data about which cells contain obstacles (large and small buildings, other vehicles, etc).
As for the pathfinding itself, can I get away with old fashioned A*? I'm using C# here if that makes a difference. I've looked for pathfinding libraries but the ones I've found are fairly useless.
Vehicle pathfinding in large height map with obstacles
I'll try to be a help here as much as I can. A* is just an algorithm that finds the best route from its given heuristics (terrain type and etc...) It can be used in grid-based maps as well as graph-based (think nav-meshes).
Given your quadtree (depending how it stores data), you can tell your A* algorithm how many obstacles it may have and include that in the heuristic equation.
So, regarding your question, A* can definitely work but the you'll have to determine what's the "worst type of terrain" as well as the "best".
Since you're using a height-map, you could probably get away with some sort of funnel algorithm applied to your path-finding system of choice. To avoid obstacles, you can (as stated before), include those in your algorithm-determining system or use dynamic avoidance to apply forces to "push" your agent away from them.
Given your quadtree (depending how it stores data), you can tell your A* algorithm how many obstacles it may have and include that in the heuristic equation.
So, regarding your question, A* can definitely work but the you'll have to determine what's the "worst type of terrain" as well as the "best".
Since you're using a height-map, you could probably get away with some sort of funnel algorithm applied to your path-finding system of choice. To avoid obstacles, you can (as stated before), include those in your algorithm-determining system or use dynamic avoidance to apply forces to "push" your agent away from them.
My concern about using A* for a vehicle is that it doesn't naturally consider vehicle handling, momentum etc. According to A* you'd turn on a dime to take the shortest path rather than take a longer gentle curve. Of course you could build a non-grid-based graph for A* in a way that takes that into consideration, e.g. choose choke points and bends as your nodes, treat straight flat areas as "low cost" edges, treat hilly or windy areas as "high cost" edges, then apply path smoothing after.
My concern about using A* for a vehicle is that it doesn't naturally consider vehicle handling, momentum etc. According to A* you'd turn on a dime to take the shortest path rather than take a longer gentle curve. Of course you could build a non-grid-based graph for A* in a way that takes that into consideration, e.g. choose choke points and bends as your nodes, treat straight flat areas as "low cost" edges, treat hilly or windy areas as "high cost" edges, then apply path smoothing after.
From what I usually see, A* finds the best path and the agent (or vehicle) seeks the next path-node. So A* shouldn't be responsible for the vehicle portion, the vehicle should.
I think that's being simplistic. If you're looking for the shortest path, fine. A* will find it. If you're looking for a realistic path, A* is not it unless your game world is mostly open space. On a day with light traffic, a highway that is 20% longer than taking local streets could easily take 50% less time to travel because vehicles like wide straight roads. And let's not forget performance handling characteristics of a vehicle. A semi-trailer might technically be able to travel narrow windy lanes, but some corners might require 20 point turns, and if it needs to be re-routed for any reason it would be unable to turn around. A* assumes that all paths to a point are equal as long as the cost of the paths are equal. Apart from the costs and the open list, A* is stateless. For a vehicle, facing the right way when it reaches that point is of huge value.
When pathfinding with A* you could make nodes that require sharp turns cost more. Like you would compute how long it takes to go from the previous node to the current node given the approximated direction and speed at the previous node. Take more nodes into account for better paths.
Might not be the best way to do it though.
Might not be the best way to do it though.
The problem is that people use A* because it's efficient, and that efficiency depends upon only exploring a node once. If you investigate a node multiple ways depending upon how they got there, you potentially get a combinatorial explosion in the amount of work you have to do.
I see two possible approaches:
1. Each node is only expanded once, but each node stores a "direction of travel" (how it was first reached) and it gets to explore neighbours in the direction of travel before anyone else that has the same cost to get to that neighbour.
2. You categorise the terrain itself based on it's straightness or bendiness. This would likely mean a coarser A* graph with many assumptions built into the edge costs. Maybe even use a hierarchical system, because coarser levels have a better idea where you're going, and therefore what constitutes "bendy".
As you can imagine, they both have flaws. ;)
I see two possible approaches:
1. Each node is only expanded once, but each node stores a "direction of travel" (how it was first reached) and it gets to explore neighbours in the direction of travel before anyone else that has the same cost to get to that neighbour.
2. You categorise the terrain itself based on it's straightness or bendiness. This would likely mean a coarser A* graph with many assumptions built into the edge costs. Maybe even use a hierarchical system, because coarser levels have a better idea where you're going, and therefore what constitutes "bendy".
As you can imagine, they both have flaws. ;)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
