A river puzzle
Try to find a route from the light grey dot (west) to the dark grey dot (east). To the north there is a big lake, to the south there is sea. In between there is a river with several branches. The light dots in the river are fords suitable for crossing. Now ford A would look like an easy pick - but taking that leads to a dead end. Ford C is far away but would make the easiest route. Ford B is a good start, and then to ford D - but then what; with faulty rules the algorithm might end up picking the ford E instead of F, thus ending up in going circles crossing the same river again and again... All this is very simple for human brain, and an algorithm like A* would eventually solve the puzzle. So, my challenge was to find simple heuristic rules to plan a route.
photo by:
Erkka Lehmus
back to:
Blog entries
Recent comments
Follow us
Elk News - the email newsletter
Subscribe to the Elk RSS feed, including blog posts, pictures and videos.
Titles only
Full content
Comments aren't included in these feeds. For them you can click the RSS icon in the Recent Comments box.
Our videos at
YouTube
Vimeo
Comments
Can you measure the distance and the work needed to cross the fords?
Trying all the routes you have two choices: depth first search and breadth first search. In depth first you go as far as you can until you find the goal or get stuck in dead end. In breadth first search you check all the possibilities at hand before you advance. The latter uses lot of memory and the first can go in an eternal loop.
The first idea would be to memorize the passed fords and avoid one that you've passed already. If it's possible.
If you know you can get some solution in tolerable time and you can measure how long you've gone already, a branch and bound algorithm would be a good choice. Find the goal and measure the distance (counting the work crossing the fords) and save it as the best solution. Then go on again in backtracking (when all possibilities from this point are exhausted, go back to the previous point and try other available routes if there are any) but every time you've gone as far as your present best solution, go back because there are no better routes ahead.) If you find a better route, save it as the best route and go on until you find an optimum.
Again if you want to avoid loops and you can keep track of the distance you've gone, one choice that combines depth first and breadth first is iterative deepening search that wastes a bit of computing resources but essentially works as breadth first but uses as little memory as depth first. On the other hand, in iterative deepening you have to know some good guesses about how long you're going.
Iterative deepening goes like this: For simplicity's sake let's assume the distances are simple integers. First try all the solutions with distance 1, then solutions of distance 2 etc. Eventually the first route you'll find will be the shortest one.
I'm not sure what you need but hope this helps.
Speaking of details; the exact scenario was like this: I was working with this kind of a map, but it had a ford in the river branch after ford A. So I was able to approach ford E from south-west. After crossing ford E, my algorithm went onwards until hitting the next branch of river. And from that point the algorithm went following the river both up and down - looking for a closest ford. Well, going upwards, following every curve of the river the algorithm found ford D and decided to cross it...
Actually, to be sure, I wrote a small area recognition algorithm, West from fords D and E is area X, and to the east there is area Y, and behind ford F there is area Z. Now, when picking a ford to cross, I can use heuristic rule: "does this ford take me back to the area I was before, or does this take me to a new area?" and this way avoid going into a loop.
But reading your description I think I could drop the area recognition and use a loop detection instead. If the algorith finds that it is crossing a same ford it has already crossed, it would mark the route as dead end and take steps back, going to test the next alternatives. Let's see =)
If you treat the fords as nodes on a graph and want to find the shortest path, you're likely to end up using something like Dijkstra's algorithm or A*.
But doesn't that require that the algorithm already knows that what are the possible connections between different nodes? I mean, if I just take the [x,y] positions of each ford, it doesn't tell me that to what river branch does which ford belong. Oh, but maybe I have to test this approach too.
I think that I have to make the algorithm so that it has room for many different alternatives and AI to pick a different route according to different criteria. For example, a peaceful fisher going to a lake would prefer the shortest route. But a bunch of raiders might want to avoid open terrains and try to stay hidden, sneaking upon their destination and maybe even choosing a unexpected route...
Why not just give different creatures different values for terrain distance? For example 1 km of open terrain might be 1 km for fisher but 10 km for raider, and shielded terrain 1 km for both.
Determining connectivity is essentially what you are doing in the example. You can't know that A has no direct path to D, E, F without checking somehow. Once this is done, finding a valid path is a fairly simple matter. Such a graph could be expanded upon to include nodes with various data and priorities. This could influence the actual path taken without needing to change the pathfinding algorithm. More weight could be given to a well traveled path or animals could attempt to avoid a path for some reason.
A navgraph created at worldgen should take away a lot of strain that pathfinding can put on the system.
Tommi and Ken, thanks for ideas - they have helped me to clarify my thoughts.
I'm glad if I was of any help. And don't worry if it takes some thinking. There's actually a mathematical proof that there's no universally working heuristic method.
Pages
Add new comment