Pathing algorithm conundrum
Hello
I have been studying pathing algorithms suchs as A * and Dijkstra's, and for the most part I believe I understand their basic concepts. However while thinking of methods of application, I thought... What if there was a map of unknown yet definite size, that you couldn't overcompensate for (for either efficiency or other reasons).
I've tried researching this with no results. Would anyone know if there is a method of operation for this sort of instance?
After thinking about it, the best I could come up with would be to start off with an educated guess based off the start and end positions, and increase the search grid incrementally if no solution is found, but this would be terribly inefficient and risks code with unexpected behavior.
I have been studying pathing algorithms suchs as A * and Dijkstra's, and for the most part I believe I understand their basic concepts. However while thinking of methods of application, I thought... What if there was a map of unknown yet definite size, that you couldn't overcompensate for (for either efficiency or other reasons).
I've tried researching this with no results. Would anyone know if there is a method of operation for this sort of instance?
After thinking about it, the best I could come up with would be to start off with an educated guess based off the start and end positions, and increase the search grid incrementally if no solution is found, but this would be terribly inefficient and risks code with unexpected behavior.
You cannot plot a path through an unknown graph; knowing your graph is prerequisite.
If you know you don't have the entire graph it is still easy enough to plot a best path through what you have; any efficiency failure outside of that is not under your control. After that, observation of behavior between unknown points is significant; use observed behavior to update your graph and work on that.
If you know you don't have the entire graph it is still easy enough to plot a best path through what you have; any efficiency failure outside of that is not under your control. After that, observation of behavior between unknown points is significant; use observed behavior to update your graph and work on that.
I have been working on this as well.
Basically I'm still building the program I intend to use it in, but the method I'm using is to take the known obstacles and basically do collision detection, treating unknown areas as perfect non-obstacles. If a collision is detected with an obstacle, a couple waypoints are created just past the corners of that obstacle, each then tests for how many collisions along the path from the waypoint to the destination, the waypoint with fewer collisions is then chosen as the immediate waypoint to head for, and the process repeats until a clear path is found to the destination. Repeat the process whenever new data about obstacles is gained.
This is simplistic view, you want to put in a couple breaks to cut sections that double back or create loops, but it is something I've not fully fleshed out myself yet. Should be a good starting point for unknown maps though. At least, no one has given negative feedback yet on my thread about it.
---
Alternatively, use A* or whatever, but only known nodes and the destination point are considered by the pathfinding algorithm. As new sections of the map are discovered, they add nodes to the map and pathfinding code runs again to find the new best path. Remember, you don't need a node for every "space" on the board, and therefore can skip unknown spaces (or wall spaces for that matter), comparing nodes by their coordinate distance when separated by unknown terrain.
---
You can also layer either of these, have a waypoints on an overworld grid of tiles (like chunks in minecraft), then simply use pathfinding on the overworld grid for "estimated waypoints, and then use a finer detailed pathfinding from unit to the nearest open/unknown space in the overworld tile containing the next overworld waypoint.
Basically I'm still building the program I intend to use it in, but the method I'm using is to take the known obstacles and basically do collision detection, treating unknown areas as perfect non-obstacles. If a collision is detected with an obstacle, a couple waypoints are created just past the corners of that obstacle, each then tests for how many collisions along the path from the waypoint to the destination, the waypoint with fewer collisions is then chosen as the immediate waypoint to head for, and the process repeats until a clear path is found to the destination. Repeat the process whenever new data about obstacles is gained.
This is simplistic view, you want to put in a couple breaks to cut sections that double back or create loops, but it is something I've not fully fleshed out myself yet. Should be a good starting point for unknown maps though. At least, no one has given negative feedback yet on my thread about it.
---
Alternatively, use A* or whatever, but only known nodes and the destination point are considered by the pathfinding algorithm. As new sections of the map are discovered, they add nodes to the map and pathfinding code runs again to find the new best path. Remember, you don't need a node for every "space" on the board, and therefore can skip unknown spaces (or wall spaces for that matter), comparing nodes by their coordinate distance when separated by unknown terrain.
---
You can also layer either of these, have a waypoints on an overworld grid of tiles (like chunks in minecraft), then simply use pathfinding on the overworld grid for "estimated waypoints, and then use a finer detailed pathfinding from unit to the nearest open/unknown space in the overworld tile containing the next overworld waypoint.
Last edited on
to path through the unknown, you pretty much have to figure out a discover and adapt algorithm, which is not "plotting a path" so much as "discovering a path". It has the potential to be painfully slow, EG a maze with 1 working path and thousands of dead ends. This is doable, and it can be done without unexpected behavior. But it can be intractable -- too many possibilities to find a working path in a reasonable time -- or degenerate, where there actually is no solution. You can improve it with educated guessing; for example take a computer map based war strategy game with a hidden map. The AI will almost always do a full search, attempting to see every pixel of the map. A human can walk say west, run into a known large obstacle (say ocean and lacking a boat), and either choose to walk up the coast looking for a land bridge or assume it is blocked. The human does not have to see every tile to know that there is a strong chance that it is ALL ocean and can use intelligence to plan a new strategy based off the discovery. Most AI can't do that (its not the problem difficulty really, its the time sink to code it vs push to market, so the AI gets a crude pass and is rarely 'good').
If the AI is dealing with unknown map area, then what is "reasonable time?"
Really, there is less map stuff for the AI to consider if they only deal with known map area, which is certainly faster than the same algorithm over the whole map. Combine that with the fact that the AI unit has to actually go places and spend moving, and can therefore update info as it is moving, I don't really see how reasonable time is an issue.
Sure it takes longer if you count time of traveling the unit all the way to the destination, but only compared to running on perfect knowledge of the map, but given the need for the unit to move and travel that distance, then the time consumption there can't be much superior to a human anyway, since the speed of travel is the limiting factor, the pathfinding algorithm only has to be able to adjust for discovered terrain as fast as new terrain is discovered in order to minimize time to destination. Calculating a path any faster than terrain discovery only gains the computer more cycles to work on other things and doesn't improve time to destination at all.
As for seeing every pixel of the map, that depends on method. For example, the collision detection method I mentioned doesn't run on checking every map tile. The AI won't be looking to examine every map tile for the absolute best path, it looks at obstacles and only those between it and it's destination/waypoints. The AI looks for A Path, and the algorithm simply refines that path as it gets new info. To use your example, if the AI finds coast, and it wants to get across, it will end up following the coast line until it has completed a loop that marks the place they are in as unconnected to the destination, which it can then use to know that any point beyond that loop is unconnected and can't be reached until tech is available to bypass that barrier. Which is exactly what a human would do (until they get distracted by a higher priority task, such as having found their opponent.).
The purpose behind choosing a destination is also a factor here. For example, while exploring, it would be a good idea to select a destination in some far off place just so a unit will follow barriers (like coastline) initially, but really, exploring nearby unknown tiles should be higher priority anyway, especially when trying to backtrack an enemy group to find their camp, the destination would be unknown tiles in the direction the enemy came from, and as obstacles are discovered, you can use the pathfinding algorithm to figure out from where the enemy units came from that would likely result in their final angle of approach, and if that hits a dead end, such as passing through a canyon into a broad open space, rather than set a destination way off in the distance, a sweep search would be made discovering the tiles of the open area starting with those closest to the canyon and slowly spreading out from there.
As for exploratory mode of simply exploring the map, checking every tile is fine, with proper prioritization, which is fairly easy. Unknown spaces nearer occupied zones and the paths between them is higher priority than the other side of an ocean. As it costs more resources to check the ocean as well, it also costs time and resources to explore, so if the AI of a strategy game for example, would use a budget for how much resources to spend on exploratory units, and therefore wouldn't be exploring the ocean until it both explored the reachable areas nearby and also could reasonably afford to do so anyway.
Really, there is less map stuff for the AI to consider if they only deal with known map area, which is certainly faster than the same algorithm over the whole map. Combine that with the fact that the AI unit has to actually go places and spend moving, and can therefore update info as it is moving, I don't really see how reasonable time is an issue.
Sure it takes longer if you count time of traveling the unit all the way to the destination, but only compared to running on perfect knowledge of the map, but given the need for the unit to move and travel that distance, then the time consumption there can't be much superior to a human anyway, since the speed of travel is the limiting factor, the pathfinding algorithm only has to be able to adjust for discovered terrain as fast as new terrain is discovered in order to minimize time to destination. Calculating a path any faster than terrain discovery only gains the computer more cycles to work on other things and doesn't improve time to destination at all.
As for seeing every pixel of the map, that depends on method. For example, the collision detection method I mentioned doesn't run on checking every map tile. The AI won't be looking to examine every map tile for the absolute best path, it looks at obstacles and only those between it and it's destination/waypoints. The AI looks for A Path, and the algorithm simply refines that path as it gets new info. To use your example, if the AI finds coast, and it wants to get across, it will end up following the coast line until it has completed a loop that marks the place they are in as unconnected to the destination, which it can then use to know that any point beyond that loop is unconnected and can't be reached until tech is available to bypass that barrier. Which is exactly what a human would do (until they get distracted by a higher priority task, such as having found their opponent.).
The purpose behind choosing a destination is also a factor here. For example, while exploring, it would be a good idea to select a destination in some far off place just so a unit will follow barriers (like coastline) initially, but really, exploring nearby unknown tiles should be higher priority anyway, especially when trying to backtrack an enemy group to find their camp, the destination would be unknown tiles in the direction the enemy came from, and as obstacles are discovered, you can use the pathfinding algorithm to figure out from where the enemy units came from that would likely result in their final angle of approach, and if that hits a dead end, such as passing through a canyon into a broad open space, rather than set a destination way off in the distance, a sweep search would be made discovering the tiles of the open area starting with those closest to the canyon and slowly spreading out from there.
As for exploratory mode of simply exploring the map, checking every tile is fine, with proper prioritization, which is fairly easy. Unknown spaces nearer occupied zones and the paths between them is higher priority than the other side of an ocean. As it costs more resources to check the ocean as well, it also costs time and resources to explore, so if the AI of a strategy game for example, would use a budget for how much resources to spend on exploratory units, and therefore wouldn't be exploring the ocean until it both explored the reachable areas nearby and also could reasonably afford to do so anyway.
Topic archived. No new replies allowed.