A* pathfinding demo

[Alex777]

  A* pathfinding



I thought some folks on here might be interested in this routine.  It demonstrates the A* pathfinding algorithm (with several different heuristics), Djikstra's algorithm for a breadth-first search, and a best-first search.  Compiles in PlayBASIC 1.089c ->PlayBASIC V1.64N.  User Instructions are in the comment block at the start.  Comments?

PlayBASIC Code: [Select]

; PROJECT : AStarDemo
; AUTHOR  :  Alex Henderson
; CREATED : 2/19/2006
; EDITED  : 2/21/2006
; ---------------------------------------------------------------------

RemStart
USER INSTRUCTIONS:
All hexes (nodes) are initialized to a movement cost = 1.  
The hex coordinates of the hex under the cursor are shown in the upper L.
Left-click to increase the movement cost, to a maximum = 9.  
Right-click to decrease the movement cost, to a minimum = 1.  
"X" key = make the hex into blocking terrain.
"S" key = select a start hex for the path.
"D" key = select a destination.
"P" key = calculate & show the path.
"F" key = save terrain map as "TerrainMap.txt".
"L" key = load "TerrainMap.txt".
The path length in hexes & the total movement cost is displayed.
You can change the start or destination & press "P" again.
copyright: public domain
RemEnd

[kevin]

Now that's seriously impressive.  Not just the path finding code, but your usage of the PB's built in helper functions is superb !.  

Excellent Demo !



Related Links:

--- Flood Fill Path finding - Demo - Source Code / Tutorial

[Alex777]

<< Now that's seriously impressive. >>

Thanks, Kevin.  Actually, what's seriously impressive are PB's fast and flexible array functions, which made implementing A* a pleasure.

Calypson, I'd be interested in your heuristic(s).  Wanna share?

[kevin]

I'm just glad some bodies using that stuff.. There somewhat abstract.. oh well  :)

[Alex777]

i think the key, for me anyway, is sticking to 1D arrays as much as possible - stacks, queues, and lists.  PB has great tools for manipulating these, although some things are not documented anywhere.

One thing we could still use is the ability to rearrange a 1D array according to the sorted order of another 1D array.  For example:

Sort2Arrays Array1(), StartElement, EndElement, Array2(), StartElement,    EndElement

where Array1() is sorted and the elements of Array2() are rearranged so that its elements remain in the same position relative to the corresponding elements in Array1().  If element 3 moves to element 7 in Array1() after sorting, then element 3 moves to element 7 in Array2() also.

[kevin]

I assume you want to store references in the one array and the sort key in the other ?

[Alex777]

Yah - I guess that's a simpler way to say it.    :rolleyes:

[Digital Awakening]

It would be nice to be able to sort a typed 1D array after a specific type. Say I have an array with units and I want to sort them after how much power they have I could sort units() after units().power.

I could probably learn a lot from that code though. Thanks Alex :)

[Bustaballs]

I tried to run it but got a compile error

[Alex777]

I tried to run it but got a compile error

Which one?

[BlinkOk]

i got a syntax error for "flushkeys" and i just deleted the line and it worked ok. i got a real old version though

[Bustaballs]

Which one?

the first post