PDA

View Full Version : SMS Pathfinding code

czar
08-08-2017, 02:31 AM
I needed a path finding routine for my little Rebelstar game project. I thought I could simply use pathfinding code already written in pascal for the job. This turned out to be more difficult that expected. Hassles with multidimensional dynamic arrays, binary heaps and other oddities that I could easily get working. I finally managed a simple routine working. I don't know who to credit for the original source code as there was no name provided.

The code is provided as is. I do not think that it is very quick. There is no cost for different terrain or diagonals implemented. However, that should not be too hard to add. Also there is no fancy interface to draw walls etc it is just bare bones.

www.numberworksnwords.com/cloud/temp/pathfinding_SMS.zip

It would be nice to have a better implementation of pathfinding - e..g., a proper Astar with terrain penalties etc

SilverWarior
08-08-2017, 08:21 PM
After throwing a quick look at the provided code it seems this is a "Sample algorithm". This path-finding algorithm is cell based and does not support different terrain weights and rarely even uses different path wight for diagonal paths.
Extending your algorithm to support diagonal movement won't be so hard as you just need to calculate values for four additional neighboring cells. But if you do plan on having different weight for diagonal movement you will have to change F,G,H to floating point values since cost for diagonal movement would be 1,41.
And if you want to add different weights based on different terrain you will have to add additional value W to each of your cells. This value stores how difficult is to traverse through certain cell and is usually stored just as multiplier. So you calculate final weight of traveling through that cell by multiplying default wight with this multiplier. So if it is larger than 1 you gain speed boost and if it smaller you are being slowed down.
Once you add diagonal movement and different cell weights you basically have a cell based A* path-finding algorithm at your hand.
You can read more about cell based A* path-finding algorithm and how it works here:
http://www.policyalmanac.org/games/aStarTutorial.htm

But I would recommend that you rather look for node-based A* path-finding algorithm instead. Why?
Main advantages of node based path-finding algorithm is that you are no longer limited to the fixed sized grid. You are able to use teleporters for creating shortcuts across your map. And since in node based path-finding each node stores possible paths to other nodes and each of these paths can have its own weight this means that you can have different path weight when going from one A to node B than when going from node B to node A. This is useful for simulating going uphill or downhill.
Another big advantage of node based path-finding is the ability to implement heuristics path-finding where multiple heuristics levels share same nodes. Somewhere on one of my computers I have nice article about heuristic path-finding but I don't find it right now.
And another advantage is that it is rather easy to modify the node graph at any time which is very useful when you game have dynamic maps.
Now the disadvantage of node based path-finding algorithm in comparison to a cell based is that it uses more memory for storing the node-graph. But on today computers I don't think that should pose much problem.

czar
09-08-2017, 12:33 AM
Thanks Silverwarrior for the pover view and the link. I am aware of the Astar stuff, to be honest I wanted a quick dropping for my little project, and my poor noggin finds pathfinding difficult to work on.

I did say "no cost for different terrain or diagonals implemented." and that it was a bare bones solution. I have implemented this simple routine for now but I may revisit later if I can solve my other majors challenges. A few other people have responded to me on the SmartMobileStudio forum to highlight two other solutions implemented in SmartMS.

phibermon
09-08-2017, 06:08 PM
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
10-08-2017, 03:09 AM
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
10-08-2017, 05:43 AM
Game specific optimization but interesting nerveless

czar
10-08-2017, 10:12 AM
@phibermon that is a pretty good description - I could see how that system would be useful to improve AI in certain games/situations

Chebmaster
13-08-2017, 10:52 AM
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
14-08-2017, 12:23 PM
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
14-08-2017, 05:22 PM
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.

phibermon
15-08-2017, 02:51 PM
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.

Ahh! thanks for the info - I didn't know much of that. Oh well it's not off topic really - many great advancements in robotics and AI have come from mimicry of the animal kingdom. The 'flow field' biasing I described seems to my mind to be an analogue of ants leaving scents - perhaps there's something useful in the bee technique?

For example instead of storing entire paths between points - you could just store the distance travelled by an entity between those two points - then when pathing to that point - compare the linear distance to the distance travelled and if it's greater than you know that there's obstacles between the start and end points. I don't know how that can be useful exactly - but perhaps store the distance travelled and a series of left/right indicators - then when the entity encounters an obstacle it pops a left/right off the stack and knows which way to turn.

To my mind it would result in an effective path followed between two points across a static terrain but with far less memory used to store that path.

it would also plug nicely into a steering algorithm. Just a thought experiment but an interesting one!

SilverWarior
15-08-2017, 05:53 PM
For example instead of storing entire paths between points - you could just store the distance travelled by an entity between those two points - then when pathing to that point - compare the linear distance to the distance travelled and if it's greater than you know that there's obstacles between the start and end points.

That reminds me of heuristic path-finding algorithms where you store known traveling distances between different neighboring key/pivot points on tem map.

Chebmaster
17-08-2017, 06:49 AM
I think the subject is better discussed on an evolutionary biology forum or some such place
I mean, ape what mother nature does and use similar hacks.

1. Cache it! If a
NPC finds a route between two points once, it memorizes it and then re-uses it without invoking pathfinding, using simple right/left hand algorithm to go around mobile obstacles. Only large deviation/delay to follow the route causes the actor to reset its cache and perform pathfinding again
Each NPC has a weighed route cache. Or all units of the same type do, in case of RTS.

2. Lazy pathfinding
Use direct movement towards the goal with right/left hand obstacle avoidance first, fill a request for the pathfinding manager that may fulfill it several ticks later

3. If a crowd of adjacent NPCS searches for a path to the same target, do it once. Select the closest NPC as the leader and make all others follow him. Use pathfinding again only if some NPCs have little progress.

4. Use a crude approximation first, before invoking A*:
- cast a virtual collider on a direct route to target using left|right hand to go around obstacles
- if it does reach the target, try smoothing the path out by casting virual colliders between points of the path 10..15 mob diameters apart.
- if it doesn't, use A*
You can even make a *tree* of paths, branching every time your collider collides with a new obstacle, one goes left other goes right.

I mean, I used pretty dumb mechanics in my 1998 FPS but it worked surprisingly well. I'll try describing what I did:

1. Levels were object soup, up to two thousand cylindrical colliders placed haphazardly on a flat plain sorted into a primitive grid to reduce the O^N. Buildings were made of sprites, physically the same cylindrical colliders

2. There was manually created graph of nav-zones to allow navigating bridges and other difficult places. The nav-zones wre cylindrical, of different width (often quite wide)

3. There was nothing like A*. Monsters periodically performed passability checks to see if they can reach their target directly. It was a costly operation consisting of casting a virtual collider along direct path, simulating all drops from ledges and checking for deadly hazards like water or lava. Only one monster per physics tick could do this.

4. All MOBs kept track of the last nav-zone they visited which was used to find path to target. The algorithm was simple:
Is my last visited nav-zone the same as as the target?
YES: move towards the target using left/right hand obstacle avoidance when colliding with something
NO: find path through the nav-zones graph, set the next nav-zone as my next destination.

Coupled with 3, this proved to be amazingly efficient. Monsters only had problems with crudely made stairs where I, the player, had to jump to get unstuck, or with narrow bridges, congesting them and slowing to a crawl.
Other than that... They surely proved to be more proactive than DooM monsters. See player? Go a roundabout way crossing two bridges over a river and then !surprise! him. Silly player, hiding in a hut. Left/right hand along the walls until entrance, oh there is no wall... Surprise!
They were, in fact, very good at appearing !suddenly! as if from nowhere.

All of that with a dozen or so nav-zones placed by hand.

I suppose in modern times your tools auto-build a sparse nav-mesh for your level in offline mode.
But do not discard the left/right hand. It's a powerful tool.

SilverWarior
17-08-2017, 03:58 PM
You call that dumb?
What you used is actually a heuristics path-finding algorithm. The only difference between yours and those found today is that you created higher heuristic level (nav-zones) manually while in todays heuristic path-finding algorithms these higher heuristics levers are created automatically using various algorithms.
So don't call your path-finding algorithm dumb mechanics because it is quite advanced path-finding algorithm.

Now you might think: But wait it seems so easy to understand.
Of course it is easy to understand. Why? Because you are using it every day in your life.

Carver413
18-08-2017, 06:23 PM
I am using a modified flood fill design at the moment,it works in 6 directions since I'm working with hex map designs at the moment. I don't know how this stacks up against the A* in general but for rts/rpg type games where you have to plot a course for multiple targets for multiple rpc's I think this method could really shine. unlike A* this routine starts at the target and floods out posibly hitting multiple npc's depending on that distance set for the target, multi targets can be plotted at the same time and shortest distance will overwrite any overlaps.So for gather's of food a single map could be generated for all the npc's in a group and would remain valid until a food source runs out. a return map would be required for unloading of course but it would remain valid until all resources in the area have been depleted.