Pathfinding

[Preppie]

I was watching an old OLC video today (https://www.youtube.com/watch?v=0ihciMKlcP8&t=2206s) and the pathfinder algorithm interested me so I thought I'd write it in BASIC.

 

The algorithm seemed overly complex to me so I adjusted it to use a single larger array for the blocks to check with a pointer to the next block to check and a pointer to where the next block is to be added.  Doing it this way instead of using 2 smaller arrays makes the code simpler and faster, and there's no messing around with duplicates.

 

You could save space by making a smaller array and have the pointers wrap round, but you'd end up in trouble if the pointers ever met before completing the path.

 

I wrote it in FastBasic but the code will also run in TurboBasic, you can speed it up a little in FastBasic by changing all the var=var+1 to inc var.

 

When you run the program it will display a screen with a start and end point, then show the shortest path.  You can then use the joystick to add and remove walls and when you want to find the path again simply move the cursor to the top left corner and press trigger to restart the pathfinding.

 

I wrote it in GR.2 to give the same number of blocks as in the video (15*16=20*12) and then adjusted it a little to run in GR.0.  I've added the 2 .xex files and 2 text files with the code.

 

Hope someone finds this interesting and maybe useful.

 

pathfinder.xex pathfinderbig.xex pathfinder.TXT pathfinderbig.TXT

[dmsc]

Hi!

 

1 hour ago, Preppie said:

I was watching an old OLC video today (https://www.youtube.com/watch?v=0ihciMKlcP8&t=2206s) and the pathfinder algorithm interested me so I thought I'd write it in BASIC.

 

The algorithm seemed overly complex to me so I adjusted it to use a single larger array for the blocks to check with a pointer to the next block to check and a pointer to where the next block is to be added.  Doing it this way instead of using 2 smaller arrays makes the code simpler and faster, and there's no messing around with duplicates.

 

You could save space by making a smaller array and have the pointers wrap round, but you'd end up in trouble if the pointers ever met before completing the path.

 

I wrote it in FastBasic but the code will also run in TurboBasic, you can speed it up a little in FastBasic by changing all the var=var+1 to inc var.

 

When you run the program it will display a screen with a start and end point, then show the shortest path.  You can then use the joystick to add and remove walls and when you want to find the path again simply move the cursor to the top left corner and press trigger to restart the pathfinding.

 

I wrote it in GR.2 to give the same number of blocks as in the video (15*16=20*12) and then adjusted it a little to run in GR.0.  I've added the 2 .xex files and 2 text files with the code.

 

Hope someone finds this interesting and maybe useful.

 

pathfinder.xex 1.9 kB · 2 downloads pathfinderbig.xex 1.92 kB · 2 downloads pathfinder.TXT 2.19 kB · 1 download pathfinderbig.TXT 2.24 kB · 1 download

Here is a slightly faster version, with two changes:

- Factorize the routine that checks the next possible route and sets the score, using less array indirection makes it faster.

- Ends the pathfind loop if we already reached the goal, so you don't fill the entire array.

 

Also, I compiled it with my FastBasic to assembler compiler, for faster speed yet  . Works great:

 

 

 

Attached the program source and compiled.

 

pathfinderbig.TXT pathfinderbig.xex

[Preppie]

Thanks DMSC, that really useful for having a static start/end point.  But what I really like about this is that once it's done the initial analysis you can move the start point anywhere and find your way to the end point  really fast (eg. drop troops anywhere on the map and they can move to a fort).

 

Is that FastBasic to assembler compiler available on github or is it a private script atm?

 

Also, I altered my initial program a little to show the 'wave'

 

pathfinderdisplay.xex pathfinderdisplay.txt

[dmsc]

Hi!

1 hour ago, Preppie said:

Thanks DMSC, that really useful for having a static start/end point.  But what I really like about this is that once it's done the initial analysis you can move the start point anywhere and find your way to the end point  really fast (eg. drop troops anywhere on the map and they can move to a fort).

 

Is that FastBasic to assembler compiler available on github or is it a private script atm?

 

Yes, it is in a branch: https://github.com/dmsc/fastbasic/tree/WIP-compiler

 

Have Fun!

 

[Preppie]

I was wondering if I could get the pathfinder routine to work without having to do the long recalculation everytime and came up with this.

 

Basically, everytime you step on a square you increase that squares value, making it less likely to be taken next time it's one of the choices.  So now, every time you draw some barriers and ask it to find a path it will do so without any recalculating.  This will probably not find the fastest route, and will often run around in circles for a while, but it should eventually get to the end.

 

 

pathfinderinstant.xex

[xxl]

not good

atarivid.7z

[Preppie]

Well, I did say it would go round in circles a bit

[Preppie]

If you want the fastest direct route then the previous examples work perfectly but require some pre-calculating every time you add barriers.  If you want to add barriers and still find the target without recalculating then this routine works as long as you don't mind a bit of frenzied running around.

 

 

[Atlan_Roland]

While looking for some pathfinding solution for my Ultima V NPCs ( https://atariage.com/forums/topic/319655-ultima-v-world-explorer-in-antic-mode-e/page/2/?tab=comments#comment-4903483 ) i came across this:

 

It's quite fast in Mad Pascal; so it might be a first solution for wandering NPCs 

 

Thank you for putting this up Preppie!

 

Attached my Mad Pascal conversion:

 

 

 

pathfinder.pas pathfinder_mp.xex

[Preppie]

Thanks, glad it came in handy.

[rdefabri]

Qhat if the target is moving?  Would the same algorithm work?

[Preppie]

If the target is moving it won't work, you'll need to recalculate after every move.  What this routine does is allow your starting point to be anywhere and still find the route to a static target (eg. lots of enemies on a map trying to find a castle)