SMS Pathfinding code

[phibermon]

There's an interesting addition that's linked to flow fields - when you perform a lot of path finding over an area - you can 'touch' an additional bias variable in each cell and use this additional variable as part of the heuristic calculation at each point. For every cell you look at - minus a small amount from the bias value - then when the final path is found or even better when it's actually walked by an entity - you increase this bias value by twice the amount for every cell that's actually visited.

This has the effect of increasing the bias for cells that are walked and decreasing it for cells that are rejected.

Little corners and dead ends end up with very low biases and are rarely checked, because hardly any entities get successful paths through them and thus don't bias them. A corridor connecting two parts of a base would have big bias value etc.

So ultimately you get a kind of 'heat map' of the most regularly traversed cells and the heuristic bias means that these cells are considered first when path finding - greatly reducing the number of cells that are actually checked for all but the most uncommon of paths.

To make it a true flow field - instead of storing this bias heuristic as a single number - store it as a vector and add the direction the path takes over that cell as a bias vector - so you get further reductions in places where just a distance heuristic alone wouldn't favour one or the other direction.

I hope that makes sense - the idea is to check as few cells as possible.

--

Another useful technique is to store previous paths, each path themselves having a bias. Then when you path from one point to another - before walking the cells, you run through the start/end points of stored paths - from the most strongly biased paths to the least biased paths - and you see if your destination and your starting point are close to the start and end of any existing path.

If it is? then just work out the path to get to and from either end of that existing path - then you've just turned a big expensive path calculation into two small ones and a couple of linked list insertions.

It can get complicated with path merging - minimising how often it happens for different biases etc - but it's interesting

[SilverWarior]

I hope that makes sense - the idea is to check as few cells as possible.

I believe this approach is being used in game Prison Architect and until now I haven't really understood how it works. But thanks to your description I do now.

[laggyluk]

Game specific optimization but interesting nerveless

[czar]

@phibermon that is a pretty good description - I could see how that system would be useful to improve AI in certain games/situations

[Chebmaster]

Creatures IRL use actual pathfinding as the last resort to conserve brain power.
Normally they rely on life-hacks like memorizing a route once found (even if it's not optimal), the right/left hand rule for going around obstacles and other such.

For example: I had a dog once, many years ago. I was walking it, and it ran behind a wire mesh fence with a hole in it. Then followed me until she ran into a corner. Whoops.
So what did she do seeing me going ahead? She whined, she ran back and forth along the fence several times (using right/left hand algorithm of obstacle avoidance). Then she looked at me one more time and I practically felt that click in her brain as she dashed hurriedly back to the hole.
The question is: did she use A* or was it a modified breadcrumbs algorithm as she clearly knew the path I followed and her point of departure from that path?

[phibermon]

Creatures IRL use actual pathfinding as the last resort to conserve brain power.
Normally they rely on life-hacks like memorizing a route once found (even if it's not optimal), the right/left hand rule for going around obstacles and other such.

For example: I had a dog once, many years ago. I was walking it, and it ran behind a wire mesh fence with a hole in it. Then followed me until she ran into a corner. Whoops.
So what did she do seeing me going ahead? She whined, she ran back and forth along the fence several times (using right/left hand algorithm of obstacle avoidance). Then she looked at me one more time and I practically felt that click in her brain as she dashed hurriedly back to the hole.
The question is: did she use A* or was it a modified breadcrumbs algorithm as she clearly knew the path I followed and her point of departure from that path?

Ha that's a wonderful observation - I think the subject is better discussed on an evolutionary biology forum or some such place - even more incredible to my mind is the ability of birds to travel half way round the world to the same lake - or even more incredible is frogs returning to the pond from which they spawned in order to mate - I'd say breadcrumbs but a few years ago the garden at my old house was completely remodelled - new fences put up and a gate installed at the back of the garden.

Next year I was outside and I noticed frogs hopping in from under the gate to get to the pond - a path that was previously completely blocked off by the topography of the garden - did they breadcrumb to the general vicinity and then left-right until they found a gap? did those frogs just happen to come from that direction and get lucky?

[SilverWarior]

Next year I was outside and I noticed frogs hopping in from under the gate to get to the pond - a path that was previously completely blocked off by the topography of the garden - did they breadcrumb to the general vicinity and then left-right until they found a gap? did those frogs just happen to come from that direction and get lucky?

As far as frogs go. They have extremely powerful smelling capability. In fact it is so powerful that they can detect increased moisture in the air. So when wind blows over your pond the air is moisturized and then carried away. Frogs can then follow this trail of moisturized air back to your pond. And they can do this from a range of even up to 10 km or 6 miles.
And frogs are not the only animals capable of this. My mom was born in a village which was founded about 300 years ago when during the drought season pigs (which also have very acute smell) wandered over 15 km (roughly 10 miles) to a fresh water spring which was the only natural spring that season that hasn't dried. In fact from the time of when this spring was discovered for the first tim and till today nobody has ever seen it dry up yet.

Any way if you look at all the different way animals use for path-finding. Well let us just say that in your lifetime you probably won't be able to write algorithms that mimic most of them.
Here are just some of the most amazing ways animals use for orientation and path-finding:
1. Birds are known for being able to detect earth magnetic field and thus location of earths magnetic poles. This allows them to navigate great distances without much problems. But scientists are warning us that with all the electromagnetic interference we are causing we might be eventually causing them havoc in their navigation. And birds are not the only animals that have this ability. Many others have but are not so dependent on it like the birds are.
2. Bees remember the path they took from their hive to the flower by simply remembering how long they flew in straight lien and when they turned and into which way. They also have a clever way of communicating this information to other bees through so called "bee dance".
3. Ants always leave chemical trail behind them so they can always return back to the nest. Even ore by manipulating the chemical they use on this trail they are leaving specific message of what kind od destination does this path leaves to (food, danger, etc).

Sorry for going a bit off-topic but for me this is interesting stuff especially when I see computers trying to mimic/simulate it.