Alternatives to A*? - GameCreators Forum

Author

Message

Fallout

22

Years of Service

User Offline

Joined: 1st Sep 2002

Location: Basingstoke, England

Posted: 22nd Feb 2006 15:57

Link

Hmmm. I keep searching online and every resource I find keeps mentioning alternatives to A*, but I can't find the actual alternatives. The reason why I'm looking for alternatives is because A* is a bit overkill for ODF, as the only thing the units need to negotiate is the odd building (and each other) - not complex networks of walls.

Has anyone got any names of alternative algorithms so I can hunt them down on google?

Just want to get an idea of all the different methods, then maybe use the best one or come up with a hybrid. Currently I have some complex ray casting/line of sight things which I think will get too slow with too many units.

Back to top

Profile PM

Pincho Paxton

21

Years of Service

User Offline

Joined: 8th Dec 2002

Location:

Posted: 22nd Feb 2006 16:05 Edited at: 22nd Feb 2006 16:07

Link

Divide the landscape into square zones. Then run distance routines in just the zones that a tank occupies, and the zones all around it. That's 9 zones in all, so make them quite small. You could do that in just the direction that it is facing so you have just 6 zones, but you probably have reverse gear in the tanks.

Back to top

Profile PM Email Website

IanG

20

Years of Service

User Offline

Joined: 25th Sep 2004

Location: Cyberspace

Posted: 22nd Feb 2006 18:04

Link

http://en.wikipedia.org/wiki/Shortest_path_problem
gots some links to some info on some path finding stuff

amd athlon xp 2600+,1280mb,FX 5200 128mb,200gb,xp pro sp2

Back to top

Profile PM

IanM

Retired Moderator

22

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 22nd Feb 2006 19:06

Link

A simple 'move forwards, but if you can't, move sideways' may work for you:

sync on
sync
sync
sync rate 1

global dim Grid(10,10) as dword

for y = 3 to 7
   Grid(5, y) = rgb(255, 255, 255)
next

global StartX = 1
global StartY = 5
global TargetX = 9
global TargetY = 5

global CurrentX = StartX
global CurrentY = StartY
global CurrentFlip = 1

do
   DrawGrid()

if CurrentX = TargetX and CurrentY = TargetY
      CurrentX = StartX
      CurrentY = StartY
   else
      SaveX = CurrentX
      SaveY = CurrentY
      MoveMade = 0

DistanceX = TargetX - CurrentX
      DistanceY = TargetY - CurrentY

if abs(DistanceX) > abs(DistanceY)
         CurrentX = CurrentX + Sign(DistanceX)
      else
         CurrentY = CurrentY + Sign(DistanceY)
      endif
      if Grid(CurrentX, CurrentY) <> 0
         if CurrentX <> SaveX
            CurrentX = SaveX
            CurrentY = CurrentY + CurrentFlip
         else
            CurrentY = SaveY
            CurrentX = CurrentX + CurrentFlip
         endif
      else
         CurrentFlip = 0 - CurrentFlip
      endif
   endif

sync
loop

function Sign(Value as integer)
   if Value < 0 then exitfunction -1
   if Value then exitfunction 1
endfunction 0

function DrawGrid()
   for x=0 to 10
      for y=0 to 10
         Colour = Grid(x, y)
         if Colour = 0 then Colour = rgb(0, 0, 0)
         box x*10, y*10, x*10+10, y*10+10, Colour, Colour, Colour, Colour
      next y
   next x
   box StartX*10, StartY*10, StartX*10+10, StartY*10+10, rgb(255, 0, 0), rgb(255, 0, 0), rgb(255, 0, 0), rgb(255, 0, 0)
   box TargetX*10, TargetY*10, TargetX*10+10, TargetY*10+10, rgb(0, 255, 0), rgb(0, 255, 0), rgb(0, 255, 0), rgb(0, 255, 0)
   box CurrentX*10, CurrentY*10, CurrentX*10+10, CurrentY*10+10, rgb(0, 0, 255), rgb(0, 0, 255), rgb(0, 0, 255), rgb(0, 0, 255)
endfunction

+ Code Snippet

sync on
sync
sync
sync rate 1

global dim Grid(10,10) as dword

for y = 3 to 7
   Grid(5, y) = rgb(255, 255, 255)
next

global StartX = 1
global StartY = 5
global TargetX = 9
global TargetY = 5

global CurrentX = StartX
global CurrentY = StartY
global CurrentFlip = 1

do
   DrawGrid()

   if CurrentX = TargetX and CurrentY = TargetY
      CurrentX = StartX
      CurrentY = StartY
   else
      SaveX = CurrentX
      SaveY = CurrentY
      MoveMade = 0

      DistanceX = TargetX - CurrentX
      DistanceY = TargetY - CurrentY

      if abs(DistanceX) > abs(DistanceY)
         CurrentX = CurrentX + Sign(DistanceX)
      else
         CurrentY = CurrentY + Sign(DistanceY)
      endif
      if Grid(CurrentX, CurrentY) <> 0
         if CurrentX <> SaveX
            CurrentX = SaveX
            CurrentY = CurrentY + CurrentFlip
         else
            CurrentY = SaveY
            CurrentX = CurrentX + CurrentFlip
         endif
      else
         CurrentFlip = 0 - CurrentFlip
      endif
   endif

   sync
loop

function Sign(Value as integer)
   if Value < 0 then exitfunction -1
   if Value then exitfunction 1
endfunction 0

function DrawGrid()
   for x=0 to 10
      for y=0 to 10
         Colour = Grid(x, y)
         if Colour = 0 then Colour = rgb(0, 0, 0)
         box x*10, y*10, x*10+10, y*10+10, Colour, Colour, Colour, Colour
      next y
   next x
   box StartX*10, StartY*10, StartX*10+10, StartY*10+10, rgb(255, 0, 0), rgb(255, 0, 0), rgb(255, 0, 0), rgb(255, 0, 0)
   box TargetX*10, TargetY*10, TargetX*10+10, TargetY*10+10, rgb(0, 255, 0), rgb(0, 255, 0), rgb(0, 255, 0), rgb(0, 255, 0)
   box CurrentX*10, CurrentY*10, CurrentX*10+10, CurrentY*10+10, rgb(0, 0, 255), rgb(0, 0, 255), rgb(0, 0, 255), rgb(0, 0, 255)
endfunction

You might also want to try a line-of-sight type system. Scan forwards until you hit the target or an obstacle. If it was an obstacle, scan again, but 5 degrees left until you are past it or hit it. If you hit it again, try 5 degrees right, then 10 degrees left, 10 degrees right etc. Once you are past it, scan towards your target again. You will end up with a set of waypoints to your target. The attached png might make this a little clearer ... certainly that isn't the best explanation I've ever made

For free Plug-ins and source code http://www.matrix1.demon.co.uk

Attachments

Login to view attachments

Back to top

Profile PM Email Website

Mnemonix

21

Years of Service

User Offline

Joined: 2nd Dec 2002

Location: Skaro

Posted: 22nd Feb 2006 19:34

Link

Thats an algorithm that might be worth trying. Its raycasting. If you adopt a grid system then the raycasting can be optimized and quicker.

WE SHALL BECOME ALL POWERFUL! CRUSH THE LESSER RACES! CONQUER THE GALAXY! UNIMAGINABLE POWER! UNLIMITED RICE PUDDING ! ! ! ETC. ! ! ! ETC.! ! !

Back to top

Profile PM Email Website

JoelJ

21

Years of Service

User Offline

Joined: 8th Sep 2003

Location: UTAH

Posted: 22nd Feb 2006 19:47

Link

Fallout:
i checked you WIP thead and watched all the videos... very very very professional looking

This just in: White lab coats cause cancer in mice. Details comming soon.

Back to top

Profile PM Website

Fallout

22

Years of Service

User Offline

Joined: 1st Sep 2002

Location: Basingstoke, England

Posted: 22nd Feb 2006 20:22

Link

Thanks Joel.

Hopefully the gameplay will live up to the visuals.

Thanks for the suggestions too. I've sort of gone along a combination between the node and raycasting route. I have no idea if it'll run well, but I'm gonna use the raycasting method to detect collision and then get the unit to follow node "detour" paths around buildings. I'm not using a grid of any kind, which I think is nicer, but is making this stuff more complicated.

Hmmm. We'll see how it goes. So far I've just finished designing a node grid for one part of the level. I'll try and implement it this evening and tomorrow.

Back to top

Profile PM

Jeku

Moderator

21

Years of Service

User Offline

Joined: 4th Jul 2003

Location: Vancouver, British Columbia, Canada

Posted: 22nd Feb 2006 22:10

Link

Quote: "You might also want to try a line-of-sight type system."

Raycasting can be *very* taxing on a game. I remember the raycaster built into the Meqon physics engine was just abysmal, as I was trying to do what IanM suggested to get my car to stay on the track.

We soon ditched the raycasting and went for something else.

Automaton Games website has been revamped! Check it out!

Back to top

Profile PM Website

Fallout

22

Years of Service

User Offline

Joined: 1st Sep 2002

Location: Basingstoke, England

Posted: 22nd Feb 2006 22:19 Edited at: 22nd Feb 2006 22:21

Link

I've managed to get the ray casting setup so that only a couple of rays are cast per unit, about once a second against about 4 meshes of 20polys. How that holds up with 50 or so moving units, I'll have to see. So far, so good.

Edit: IanM, somehow I missed your codebox!

Thanks for that!

Back to top

Profile PM

Jess T

Retired Moderator

21

Years of Service

User Offline

Joined: 20th Sep 2003

Location: Over There... Kablam!

Posted: 23rd Feb 2006 01:15

Link

If you want to use A* anyway, and a blisteringly fast one, try mine:

remstart

`For the A*
Type openclosed
   traversable As Boolean
   parent As Integer
   parentCount As Integer
   open As Integer
   closed As Integer
   f As Integer
   g As Integer
   h As Integer
EndType

Type floodfill
   accessable As Boolean
   location As Integer
EndType

remend

`x and y represent the Width and Height respectively
`If you had a zero-based array from 0 to 4 in both directions,
` the x = 5 and y = 5, etc.
Function _AStar_init(x As Integer, y As Integer)

Local totalSize As Integer
   totalSize = x * y

`The world map holding the passable terrain info
   Global Dim AStar_map(totalSize) As openclosed

`Obvious
   Global AStar_width As Integer
   Global AStar_height As Integer

`Used for the offset within the array to find the correct 'tile'
   Global AStar_off1 As Integer
   Global AStar_off2 As Integer

`This is the cost for moving horizontal/vertical and diagonally
   Global AStar_g_perp As Integer
   Global AStar_g As Integer

`Diagonal Movements are allowed?
   Global AStar_diag As Boolean

`Corner Cutting across obsticals is allowed?
   Global AStar_diag_Pass As Boolean

`How many items are in the Open List?
   Global AStar_total_Open As Integer

`How many items are in the Closed List?
   Global AStar_total_Closed As Integer

`Penality for turns whilst pathing ( keeps 'em straighter, and looking nicer )
   Global AStar_penalty_turn As Integer

AStar_width = x
   AStar_height = y

AStar_off1 = 0 - (AStar_width + 1)
   AStar_off2 = AStar_width - 1

AStar_g_perp = 10
   AStar_g = 14

AStar_total_Open = 0
   AStar_total_Closed = 0

AStar_penalty_turn = 0

`These arrays have to start at 1,1 rather than 0,0
   Global Dim AStar_Open(totalSize) As Integer
   Global Dim AStar_Closed(totalSize) As Integer

Global debug As Boolean
   debug = 0

EndFunction

Function _AStar_Uninit()

`The world map holding the passable terrain info
   UnDim AStar_map(0)

`These arrays have to start at 1,1 rather than 0,0
   UnDim AStar_Open(0)
   UnDim AStar_Closed(0)

EndFunction

`Value of 1 for 'terrain' is 'impassable'
`
Function _AStar_set_terrain(x As Integer, y As Integer, terrain As Boolean)

If x >= 0 And x < AStar_width And y >= 0 And y < AStar_height
      AStar_map(y * AStar_width + x).traversable = terrain
   EndIf

EndFunction

Function _AStar_get_terrain(x As Integer, y As Integer)

Local result As Integer
   result = -1

If x >= 0 And x < AStar_width And y >= 0 And y < AStar_height
      result = AStar_map(y * AStar_width + x).traversable
   EndIf

EndFunction result

Function _AStar_enable_diagonal_cutting(diag As Boolean)

AStar_diag_Pass = diag

EndFunction

`Will return a pointer to memory containing the x/y combinations of the path in this format:

`[No Nodes Ex. Start Node Inc. End Node]
`For each Node:
`  Integer [XPos in Map]
`  Integer [YPos in Map]
Function _AStar_find_path(x1 As Integer, y1 As Integer, x2 As Integer, y2 As Integer)
`x1/y1 & x2/y2 Must be 0-based array indecies

`Memory pointer to the Area holding info on the Path
   Local result As DWord
   Local tmpMem As DWord

`Have we reached x2/y2 yet?
   Local goal As Integer

`The current parent node we're at
   Local location As Integer
   Local newLocation As Integer

`Obviously, the location of the new element
   Local newElement As Integer

Local doIt As Boolean
   Local masterCut As Boolean

Local tmpf As Integer
   Local tmpg As Integer
   Local tmph As Integer

goal = y2 * AStar_width + x2
   location = y1 * AStar_width + x1

`Add our initial parent to the Open List
   AStar_binary_new(location, 0)

Local loopNum As Integer

`Keep going till we get to the goal
   Repeat

Inc loopNum

remstart ######################
If debug = 1
If (location > AStar_width * AStar_height - 1) Or (location < 0)
   Exit Prompt "Urm... Location (" + Str$(location) + ") is too big, wtf? On Loop Number " + Str$(loopNum), "Whoops!"
   End
EndIf

Set Cursor 0,0
Cls
Print "Current Location = " + Str$(location)
Print "Total Open = " + Str$(AStar_total_Open)
Sync : Sync
Wait Key
EndIf
remend `######################

`Row above current node
      For i = AStar_off1 To AStar_off1 + 2

remstart ######################
If debug = 1
If (location + i > AStar_width * AStar_height - 1) Or (location + i < 0)
   Exit Prompt "Urm... Location + i (" + Str$(location + i) + ") is too big, wtf? On Loop Number " + Str$(loopNum) + ". sx = " + Str$(x1) + ", sy = " + Str$(y1) + ", ex = " + Str$(x2) + ", ey = " + Str$(y2), "Whoops!"
   End
EndIf
EndIf
remend `######################

newLocation = location + i

If AStar_map(newLocation).traversable = 0

`Reset the value(s)
            doIt = 0
            masterCut = 0

`Work out the F, G, H values
            If i - AStar_off1 = 1
               tmpg = AStar_map(location).g + AStar_g_perp
            Else
               `Figure out the weighting for this one
               tmpg = AStar_map(location).g + AStar_g

`Can we use it, though? Does it cut a corner?
               If AStar_diag_Pass = 0
                  If i - AStar_off1 = 0
                     If AStar_map(location - 1).traversable = 1 Or AStar_map(location + AStar_off1 + 1).traversable = 1 Then masterCut = 1
                  Else
                     If AStar_map(location + 1).traversable = 1 Or AStar_map(location + AStar_off1 + 1).traversable = 1 Then masterCut = 1
                  EndIf
               EndIf

EndIf

`Don't allow it if it's corner cutting
            If masterCut = 0

tmph = AStar_get_heuristic(((newLocation) MOD AStar_width) , ((newLocation) - ((newLocation) MOD AStar_width)) / AStar_width , x2 , y2 )

tmpf = tmpg + tmph

`Need a check for if it's on the closed list already
               If AStar_map(newLocation).closed > 0
                  `If it is on the closed list, we need to check if the new values
                  ` Are better than those previously in it. If so, take it off the
                  ` closed list and put it back onto the Open list with the new values
                  If AStar_map(newLocation).f > tmpf
                     `_AStar_closed_remove(newLocation)
                     `doIt = 1
                  EndIf
               Else
                  `Check if it's already on the Open List
                  If AStar_map(newLocation).open > 0
                     `If it is, then we compare the values as for the closed list
                     If AStar_map(newLocation).f > tmpf
                        `_AStar_closed_remove(newLocation)
                        doIt = 1
                     EndIf
                  Else
                     doIt = 1
                  EndIf
               EndIf

If doIt = 1
                  AStar_map(newLocation).parent = location
                  AStar_map(newLocation).parentCount = AStar_map(location).parentCount + 1
                  AStar_map(newLocation).g = tmpg
                  AStar_map(newLocation).h = tmph
                  AStar_map(newLocation).f = tmpf
                  `Penalties for turns
                  If location - AStar_map(location).parent <> i Then AStar_map(newLocation).f = AStar_map(newLocation).f + AStar_penalty_turn
                  If AStar_map(newLocation).open = 0
                     AStar_binary_new(newLocation, 0)
                  Else
                     AStar_binary_new(newLocation, AStar_map(newLocation).open)
                  EndIf

If newLocation = goal Then location = goal : Exit

remstart ######################
If debug = 1
Print Str$(newLocation) + ", f = " + Str$(AStar_map(newLocation).f) + ", g = " + Str$(AStar_map(newLocation).g) + ", h = " + Str$(AStar_map(newLocation).h) + ", XPos = " + Str$(((newLocation) MOD AStar_width)) + ", YPos = " + Str$(((newLocation) - ((newLocation) MOD AStar_width)) / AStar_width) + ", Open = " + Str$(AStar_map(newLocation).open)
Sync : Sync
Wait Key
EndIf
remend `######################

EndIf

EndIf
      Next i

`Did we find the goal this time?
      If location = goal Then Exit

`Left and Right of current Node
      For i = -1 To 1 Step 2

remstart ######################
If debug = 1
If location + i > AStar_width * AStar_height - 1
   Exit Prompt "Urm... Location (" + Str$(location + i) + ") is too big, wtf? On Loop Number " + Str$(loopNum), "Whoops!"
   End
EndIf
EndIf
remend `######################

newLocation = location + i

If AStar_map(newLocation).traversable = 0

`Reset the value
            doIt = 0

`Work out the F, G, H values
            tmpg = AStar_map(location).g + AStar_g_perp
            tmph = AStar_get_heuristic(((newLocation) MOD AStar_width) , ((newLocation) - ((newLocation) MOD AStar_width)) / AStar_width , x2 , y2 )
            tmpf = tmpg + tmph

`Need a check for if it's on the closed list already
            If AStar_map(newLocation).closed > 0
               `If it is on the closed list, we need to check if the new values
               ` Are better than those previously in it. If so, take it off the
               ` closed list and put it back onto the Open list with the new values
               If AStar_map(newLocation).f > tmpf
                  `_AStar_closed_remove(newLocation)
                  `doIt = 1
               EndIf
            Else
               `Check if it's already on the Open List
               If AStar_map(newLocation).open > 0
                  `If it is, then we compare the values as for the closed list
                  If AStar_map(newLocation).f > tmpf
                     `_AStar_closed_remove(newLocation)
                     doIt = 1
                  EndIf
               Else
                  doIt = 1
               EndIf
            EndIf

If doIt = 1
               AStar_map(newLocation).parent = location
               AStar_map(newLocation).parentCount = AStar_map(location).parentCount + 1
               AStar_map(newLocation).g = tmpg
               AStar_map(newLocation).h = tmph
               AStar_map(newLocation).f = tmpf
               `Penalties for turns
               If location - AStar_map(location).parent <> i Then AStar_map(newLocation).f = AStar_map(newLocation).f + AStar_penalty_turn
               If AStar_map(newLocation).open = 0
                  AStar_binary_new(newLocation, 0)
               Else
                  AStar_binary_new(newLocation, AStar_map(newLocation).open)
               EndIf

remstart ######################
If debug = 1
Print Str$(newLocation) + ", f = " + Str$(AStar_map(newLocation).f) + ", g = " + Str$(AStar_map(newLocation).g) + ", h = " + Str$(AStar_map(newLocation).h) + ", XPos = " + Str$(((newLocation) MOD AStar_width)) + ", YPos = " + Str$(((newLocation) - ((newLocation) MOD AStar_width)) / AStar_width) + ", Open = " + Str$(AStar_map(newLocation).open)
Sync : Sync
Wait Key
EndIf
remend `######################

If newLocation = goal Then location = goal : Exit
            EndIf

EndIf
      Next i

`Did we find the goal this time?
      If location = goal Then Exit

`Row below current node
      For i = AStar_off2 To AStar_off2 + 2

remstart ######################
If debug = 1
If location + i > AStar_width * AStar_height - 1
   Exit Prompt "Urm... Location (" + Str$(location + i) + ") is too big, wtf? On Loop Number " + Str$(loopNum), "Whoops!"
   End
EndIf
EndIf
remend `######################

newLocation = location + i

If AStar_map(newLocation).traversable = 0

`Reset the value
            doIt = 0
            masterCut = 0

`Work out the F, G, H values
            If i - AStar_off2 = 1
               tmpg = AStar_map(location).g + AStar_g_perp
            Else
               tmpg = AStar_map(location).g + AStar_g

`Can we use it, though? Does it cut a corner?
               If AStar_diag_Pass = 0
                  If i - AStar_off2 = 0
                     If AStar_map(location - 1).traversable = 1 Or AStar_map(location + AStar_off2 + 1).traversable = 1 Then masterCut = 1
                  Else
                     If AStar_map(location + 1).traversable = 1 Or AStar_map(location + AStar_off2 + 1).traversable = 1 Then masterCut = 1
                  EndIf
               EndIf

EndIf

If masterCut = 0

tmph = AStar_get_heuristic(((newLocation) MOD AStar_width) , ((newLocation) - ((newLocation) MOD AStar_width)) / AStar_width , x2 , y2 )

tmpf = tmpg + tmph

`Need a check for if it's on the closed list already
               If AStar_map(newLocation).closed > 0
                  `If it is on the closed list, we need to check if the new values
                  ` Are better than those previously in it. If so, take it off the
                  ` closed list and put it back onto the Open list with the new values
                  If AStar_map(newLocation).f > tmpf
                     `_AStar_closed_remove(newLocation)
                     `doIt = 1
                  EndIf
               Else
                  `Check if it's already on the Open List
                  If AStar_map(newLocation).open > 0
                     `If it is, then we compare the values as for the closed list
                     If AStar_map(newLocation).f > tmpf
                        `_AStar_closed_remove(newLocation)
                        doIt = 1
                     EndIf
                  Else
                     doIt = 1
                  EndIf
               EndIf

If doIt = 1
                  AStar_map(newLocation).parent = location
                  AStar_map(newLocation).parentCount = AStar_map(location).parentCount + 1
                  AStar_map(newLocation).g = tmpg
                  AStar_map(newLocation).h = tmph
                  AStar_map(newLocation).f = tmpf
                  `Penalties for turns
                  If location - AStar_map(location).parent <> i Then AStar_map(newLocation).f = AStar_map(newLocation).f + AStar_penalty_turn
                  If AStar_map(newLocation).open = 0
                     AStar_binary_new(newLocation, 0)
                  Else
                     AStar_binary_new(newLocation, AStar_map(newLocation).open)
                  EndIf

remstart ######################
If debug = 1
Print Str$(newLocation) + ", f = " + Str$(AStar_map(newLocation).f) + ", g = " + Str$(AStar_map(newLocation).g) + ", h = " + Str$(AStar_map(newLocation).h) + ", XPos = " + Str$(((newLocation) MOD AStar_width)) + ", YPos = " + Str$(((newLocation) - ((newLocation) MOD AStar_width)) / AStar_width) + ", Open = " + Str$(AStar_map(newLocation).open)
Sync : Sync
Wait Key
EndIf
remend `######################

If newLocation = goal Then location = goal : Exit

EndIf

EndIf
      Next i

`Did we find the goal this time?
      If location = goal Then Exit

remstart ######################
If debug = 1
Ink 0,0
Box Screen Width () - 80, 0, Screen Width(), Screen Height()
Ink RGB(255,255,255),0
Text Screen Width() - 40, 0, "(" + Str$(AStar_total_Open) + ")"
For i = 1 To AStar_total_Open
   Text Screen Width() - 40, i * 20, Str$(AStar_Open(i)) + "/" + Str$(AStar_map(AStar_Open(i)).open)
Next i
Text Screen Width() - 85, 0, "(" + Str$(AStar_total_Closed) + ")"
For i = 1 To AStar_total_Closed
   Text Screen Width() - 80, i * 20, Str$(AStar_Closed(i)) + "/" + Str$(AStar_map(AStar_Closed(i)).closed)
Next i
Sync : Sync
Wait Key
EndIf
remend `######################

`Put this parent onto the Closed Heap
      _AStar_closed_add(location)

`Now, find our next Parent node by grabbing the lowest from the Open list
      location = AStar_binary_get()

remstart ######################
If debug = 1
Ink 0,0
Box Screen Width () - 80, 0, Screen Width(), Screen Height()
Ink RGB(255,255,255),0
Text Screen Width() - 40, 0, "(" + Str$(AStar_total_Open) + ")"
For i = 1 To AStar_total_Open
   Text Screen Width() - 40, i * 20, Str$(AStar_Open(i)) + "/" + Str$(AStar_map(AStar_Open(i)).open)
Next i
Text Screen Width() - 85, 0, "(" + Str$(AStar_total_Closed) + ")"
For i = 1 To AStar_total_Closed
   Text Screen Width() - 80, i * 20, Str$(AStar_Closed(i)) + "/" + Str$(AStar_map(AStar_Closed(i)).closed)
Next i
Sync : Sync
Wait Key
EndIf
remend `######################

Until (location = goal) Or (AStar_total_Open = 0)

`Ok, so we've found the final child, and as such we just track back till we get to our parent
   `[No Nodes Ex. Start Node Inc. End Node]
   `For each Node:
   `  Integer [XPos in Map]
   `  Integer [YPos in Map]

result = Make Memory(4 + (8 * AStar_map(location).parentCount))

remstart ######################
If debug = 1
Cls
Text 0,0,"Total Tiles Passed: " + Str$(AStar_map(location).parentCount)

Sync : Sync
Wait Key
EndIf
remend `######################

tmpMem = result

`The header
   (*tmpMem) = AStar_map(location).parentCount : Inc tmpMem, 4

If AStar_map(location).parentCount > 0
      `The X/Y Info
remstart
      Inc tmpMem, (8 * AStar_map(location).parentCount)

Repeat
         Dec tmpMem, 8
         (*tmpMem) = (location MOD AStar_width) : Inc tmpMem, 4
         (*tmpMem) = (location - (location MOD AStar_width)) / AStar_width : Dec tmpMem, 4
         location = AStar_map(location).parent
      `Keep going till the next parent is the start square, we don't need that one
      Until location = y1 * AStar_width + x1
remend
      newLocation = location
      Repeat
         (*tmpMem) = (newLocation MOD AStar_width) : Inc tmpMem, 4
         (*tmpMem) = (newLocation - (newLocation MOD AStar_width)) / AStar_width : Inc tmpMem, 4
         newLocation = AStar_map(newLocation).parent
      `Keep going till the next parent is the start square, we don't need that one
      Until newLocation = y1 * AStar_width + x1

EndIf

`Clean up so there's no conflict's next time we try to run it
   For i = 1 To AStar_total_Open
      AStar_map(AStar_Open(i)).f = 0
      AStar_map(AStar_Open(i)).g = 0
      AStar_map(AStar_Open(i)).h = 0
      AStar_map(AStar_Open(i)).parentCount = 0
      AStar_map(AStar_Open(i)).open = 0
      AStar_Open(i) = 0
   Next i

For i = 1 To AStar_total_Closed
      AStar_map(AStar_Closed(i)).f = 0
      AStar_map(AStar_Closed(i)).g = 0
      AStar_map(AStar_Closed(i)).h = 0
      AStar_map(AStar_Closed(i)).parentCount = 0
      AStar_map(AStar_Closed(i)).closed = 0
      AStar_Closed(i) = 0
   Next i

AStar_total_Closed = 0
   AStar_total_Open = 0

EndFunction result

Function _AStar_closed_remove(index As Integer)

AStar_map(AStar_Closed(index)).closed = 0
   AStar_map(AStar_Closed(index)).open = 0
   AStar_Closed(index) = 0

If AStar_total_Closed < 0
      If File Exist("Error.txt") Then Delete File "Error.txt"
      Open To Write 1, "Error.txt"
      Write String 1, "It's below BEFORE (" + Str$(AStar_total_Closed) + ") decrementing and doing its stuff"
      Close File 1
      End
   EndIf

Dec AStar_total_Closed, 1

If index <= AStar_total_Closed
      For i = index To AStar_total_Closed
         AStar_Closed(i) = AStar_Closed(i + 1)
         AStar_map(AStar_Closed(i)).closed = i
      Next i
   EndIf

If AStar_total_Closed < 0
      If File Exist("Error.txt") Then Delete File "Error.txt"
      Open To Write 1, "Error.txt"
      Write String 1, "It's below AFTER (" + Str$(AStar_total_Closed) + ") decrementing and doing its stuff"
      Close File 1
      End
   EndIf

EndFunction

Function _AStar_closed_add(value As Integer)

Inc AStar_total_Closed

remstart ######################
If debug = 1
If (AStar_total_Closed > Array Count(AStar_Closed(0))) Or (AStar_total_Closed < 0) Then Exit Prompt "Total Closed = " + Str$(AStar_total_Closed) + ", Array size = " + Str$(Array Count(AStar_Closed(0))), "Not Good!" : End
EndIf
remend `######################

AStar_Closed(AStar_total_Closed) = value
   AStar_map(value).closed = AStar_total_Closed
   AStar_map(value).open = 0

EndFunction

`reorderIndex should be zero if it's a new item,
` if it's an already existing item, it should be its index
Function AStar_binary_new(value As Integer, reorderIndex As Integer)

Local count As Integer
   Local temp As Integer

`Keep track of where in the list it has bubbled to so far
   If reorderIndex > 0
      count = reorderIndex
      `AStar_Open(count) = value
   Else
      `Reflect the new size
      Inc AStar_total_Open

remstart ######################
If debug = 1
If AStar_total_Open <= 0 Or AStar_total_Open > AStar_width * AStar_height
   If File Exist("Error.txt") Then Delete File "Error.txt"
   Open To Write 1, "Error.txt"
   For i = 0 To AStar_total_Closed
      Write String 1, Str$(AStar_Closed(i))
   Next i
   Close File 1
   Exit Prompt "Urm... AStar_total_Open (" + Str$(AStar_total_Open) + ") is too low, wtf? Info saved to Error.txt", "Whoops!"
   End
EndIf
EndIf
remend `######################

`Add the new value at the 'end' of the list
      AStar_Open(AStar_total_Open) = value

count = AStar_total_Open
   EndIf

`Repeat until it reaches the top of the list
   ` ( Or EXITs as in the 'ELSE' )
   While count >= 4

`If This one is less than its parent, then swap them
      If AStar_map(AStar_Open(count)).f <= AStar_map(AStar_Open(Int(count / 2))).f

remstart ######################
If AStar_Open(Int(count / 2)) = 0 Or AStar_Open(count) = 0 Or count < 4
   Sync : Sync
   Wait Key
   Exit Prompt "U-oh!, Value = " + Str$(value) + " No. " + Str$(Int(count / 2)) + " = " + Str$(AStar_Open(Int(count / 2))) + " No. " + Str$(count) + " = " + Str$(AStar_Open(count)) + " reorderIndex = " + Str$(reorderIndex), ":("
   End
EndIf
remend `######################

`Do the swapping
         temp = AStar_Open(Int(count / 2))
         AStar_Open(Int(count / 2)) = AStar_Open(count)
         AStar_Open(count) = temp

AStar_map(AStar_Open(count)).open = count
         AStar_map(AStar_Open(Int(count / 2))).open = Int(count / 2)

`Now we're at the 'parent's location
         count = Int(count / 2)
      Else
         `Nope, not lower, it's as high as it can go, so exit the loop
         Exit
      EndIf

EndWhile

`set the tracking variable
   AStar_map(AStar_Open(count)).open = count

EndFunction

Function AStar_binary_get()

remstart ######################
If debug = 1
If AStar_total_Open <= 0 Or AStar_total_Open > AStar_width * AStar_height
   If File Exist("Error.txt") Then Delete File "Error.txt"
   Open To Write 1, "Error.txt"
   For i = 0 To AStar_total_Closed
      Write String 1, Str$(AStar_Closed(i))
   Next i
   Close File 1
   Exit Prompt "Urm... AStar_total_Open (" + Str$(AStar_total_Open) + ") is too low, wtf? Info saved to Error.txt", "Whoops!"
   End
EndIf
EndIf
remend `######################

Local result As Integer

Local temp As Integer

Local v As Integer
   Local u As Integer

`Reset the top-most's Open track to 0 as it is about to be put on the Closed List
   AStar_map(AStar_Open(1)).open = 0

`Now, start the removal process so that our heap isn't totally screwed up
   `Move the last-most to the front
   AStar_Open(1) = AStar_Open(AStar_total_Open)
   AStar_map(AStar_Open(1)).open = 1

AStar_Open(AStar_total_Open) = 0

`Reflect the removal of one item
   Dec AStar_total_Open

`Initialize the starting place
   v = 1

`Repeat until we want to exit
   Do
      u = v

`If both the children exist ( ie, it CAN go further down the list )
      If (2*u) + 1 <= AStar_total_Open

`Select the lowest of the two children ( Notice the use of u and v )
         If AStar_map(AStar_Open(u)).f >= AStar_map(AStar_Open(2*u)).f Then v = 2*u
         If AStar_map(AStar_Open(v)).f >= AStar_map(AStar_Open((2*u) + 1)).f Then v = (2*u) + 1

Else
         If (2*u) <= AStar_total_Open
            `Check if the cost is greater than the child
            If AStar_map(AStar_Open(u)).f >= AStar_map(AStar_Open(2*u)).f Then v = 2*u
         EndIf
      EndIf

`Now, if we've found a child smaller than the parent, swap them
      If u <> v
         temp = AStar_Open(u)
         AStar_Open(u) = AStar_Open(v)
         AStar_Open(v) = temp
         `And swap the tracking variables also
         AStar_map(AStar_Open(u)).open = u
         AStar_map(AStar_Open(v)).open = v
      Else
         `Whoops, the parent is in the right spot, let's exit!
         Exit
      EndIf
   Loop

`Get the top-most from the heap
   result = AStar_Open(1)

EndFunction result

Function AStar_get_heuristic(x1 As Integer, y1 As Integer, x2 As Integer, y2 As Integer)

result As Integer
   dx As Integer
   dy As Integer
   min As Integer

dx = Abs(x2 - x1)
   dy = Abs(y2 - y1)

If dx < dy Then min = dx Else min = dy

`diagdistance*min(|dx|,|dy|) + orthodistance*||dx|-|dy||

result = (AStar_g * min) + (AStar_g_perp * Abs(dx - dy))

`   result = (dx + dy) * AStar_g_perp

EndFunction result

remstart
Function _AStar_flood_fill(x1 As Integer, y1 As Integer)

Local totalFilled As Integer
   Local location As Integer

Dim AStar_flood(AStar_width * AStar_height) As floodfill

Inc totalFilled
   AStar_flood(totalFilled).location = y1 * AStar_width + x1
   AStar_flood(totalFilled).accessable = 1

For m = 1 To totalFilled

location = AStar_flood(m).location

`Row above current node
      For i = AStar_off1 To AStar_off1 + 2
         If AStar_map(location + i).traversable <> 1 `And NEED SOMETHING THAT CHECKS IF IT'S ALREADY BEEN ADDED!
            Inc totalFilled
            AStar_flood(totalFilled).location = location + i
            AStar_flood(totalFilled).accessable = 1
         EndIf
      Next i

`Left and Right of current Node
      For i = -1 To 1 Step 2
         If AStar_map(location + i).traversable <> 1
            Inc totalFilled
            AStar_flood(totalFilled).location = location + i
            AStar_flood(totalFilled).accessable = 1
         EndIf
      Next i

`Row below current node
      For i = AStar_off2 To AStar_off2 + 2
         If AStar_map(location + i).traversable <> 1
            Inc totalFilled
            AStar_flood(totalFilled).location = location + i
            AStar_flood(totalFilled).accessable = 1
         EndIf
      Next i
   Next m

EndFunction
remend

+ Code Snippet

remstart

`For the A*
Type openclosed
   traversable As Boolean
   parent As Integer
   parentCount As Integer
   open As Integer
   closed As Integer
   f As Integer
   g As Integer
   h As Integer
EndType

Type floodfill
   accessable As Boolean
   location As Integer
EndType

remend


`x and y represent the Width and Height respectively
`If you had a zero-based array from 0 to 4 in both directions,
` the x = 5 and y = 5, etc.
Function _AStar_init(x As Integer, y As Integer)

   Local totalSize As Integer
   totalSize = x * y

   `The world map holding the passable terrain info
   Global Dim AStar_map(totalSize) As openclosed

   `Obvious
   Global AStar_width As Integer
   Global AStar_height As Integer

   `Used for the offset within the array to find the correct 'tile'
   Global AStar_off1 As Integer
   Global AStar_off2 As Integer

   `This is the cost for moving horizontal/vertical and diagonally
   Global AStar_g_perp As Integer
   Global AStar_g As Integer

   `Diagonal Movements are allowed?
   Global AStar_diag As Boolean

   `Corner Cutting across obsticals is allowed?
   Global AStar_diag_Pass As Boolean

   `How many items are in the Open List?
   Global AStar_total_Open As Integer

   `How many items are in the Closed List?
   Global AStar_total_Closed As Integer

   `Penality for turns whilst pathing ( keeps 'em straighter, and looking nicer )
   Global AStar_penalty_turn As Integer

   AStar_width = x
   AStar_height = y

   AStar_off1 = 0 - (AStar_width + 1)
   AStar_off2 = AStar_width - 1

   AStar_g_perp = 10
   AStar_g = 14

   AStar_total_Open = 0
   AStar_total_Closed = 0

   AStar_penalty_turn = 0

   `These arrays have to start at 1,1 rather than 0,0
   Global Dim AStar_Open(totalSize) As Integer
   Global Dim AStar_Closed(totalSize) As Integer

   Global debug As Boolean
   debug = 0

EndFunction


Function _AStar_Uninit()

   `The world map holding the passable terrain info
   UnDim AStar_map(0)

   `These arrays have to start at 1,1 rather than 0,0
   UnDim AStar_Open(0)
   UnDim AStar_Closed(0)

EndFunction


`Value of 1 for 'terrain' is 'impassable'
`
Function _AStar_set_terrain(x As Integer, y As Integer, terrain As Boolean)

   If x >= 0 And x < AStar_width And y >= 0 And y < AStar_height
      AStar_map(y * AStar_width + x).traversable = terrain
   EndIf

EndFunction



Function _AStar_get_terrain(x As Integer, y As Integer)

   Local result As Integer
   result = -1

   If x >= 0 And x < AStar_width And y >= 0 And y < AStar_height
      result = AStar_map(y * AStar_width + x).traversable
   EndIf

EndFunction result



Function _AStar_enable_diagonal_cutting(diag As Boolean)

   AStar_diag_Pass = diag

EndFunction



`Will return a pointer to memory containing the x/y combinations of the path in this format:

`[No Nodes Ex. Start Node Inc. End Node]
`For each Node:
`  Integer [XPos in Map]
`  Integer [YPos in Map]
Function _AStar_find_path(x1 As Integer, y1 As Integer, x2 As Integer, y2 As Integer)
`x1/y1 & x2/y2 Must be 0-based array indecies

   `Memory pointer to the Area holding info on the Path
   Local result As DWord
   Local tmpMem As DWord

   `Have we reached x2/y2 yet?
   Local goal As Integer

   `The current parent node we're at
   Local location As Integer
   Local newLocation As Integer

   `Obviously, the location of the new element
   Local newElement As Integer

   Local doIt As Boolean
   Local masterCut As Boolean

   Local tmpf As Integer
   Local tmpg As Integer
   Local tmph As Integer

   goal = y2 * AStar_width + x2
   location = y1 * AStar_width + x1

   `Add our initial parent to the Open List
   AStar_binary_new(location, 0)

   Local loopNum As Integer

   `Keep going till we get to the goal
   Repeat

      Inc loopNum

remstart ######################
If debug = 1
If (location > AStar_width * AStar_height - 1) Or (location < 0)
   Exit Prompt "Urm... Location (" + Str$(location) + ") is too big, wtf? On Loop Number " + Str$(loopNum), "Whoops!"
   End
EndIf

Set Cursor 0,0
Cls
Print "Current Location = " + Str$(location)
Print "Total Open = " + Str$(AStar_total_Open)
Sync : Sync
Wait Key
EndIf
remend `######################

      `Row above current node
      For i = AStar_off1 To AStar_off1 + 2

remstart ######################
If debug = 1
If (location + i > AStar_width * AStar_height - 1) Or (location + i < 0)
   Exit Prompt "Urm... Location + i (" + Str$(location + i) + ") is too big, wtf? On Loop Number " + Str$(loopNum) + ". sx = " + Str$(x1) + ", sy = " + Str$(y1) + ", ex = " + Str$(x2) + ", ey = " + Str$(y2), "Whoops!"
   End
EndIf
EndIf
remend `######################

         newLocation = location + i

         If AStar_map(newLocation).traversable = 0


            `Reset the value(s)
            doIt = 0
            masterCut = 0

            `Work out the F, G, H values
            If i - AStar_off1 = 1
               tmpg = AStar_map(location).g + AStar_g_perp
            Else
               `Figure out the weighting for this one
               tmpg = AStar_map(location).g + AStar_g

               `Can we use it, though? Does it cut a corner?
               If AStar_diag_Pass = 0
                  If i - AStar_off1 = 0
                     If AStar_map(location - 1).traversable = 1 Or AStar_map(location + AStar_off1 + 1).traversable = 1 Then masterCut = 1
                  Else
                     If AStar_map(location + 1).traversable = 1 Or AStar_map(location + AStar_off1 + 1).traversable = 1 Then masterCut = 1
                  EndIf
               EndIf

            EndIf

            `Don't allow it if it's corner cutting
            If masterCut = 0

               tmph = AStar_get_heuristic(((newLocation) MOD AStar_width) , ((newLocation) - ((newLocation) MOD AStar_width)) / AStar_width , x2 , y2 )

               tmpf = tmpg + tmph

               `Need a check for if it's on the closed list already
               If AStar_map(newLocation).closed > 0
                  `If it is on the closed list, we need to check if the new values
                  ` Are better than those previously in it. If so, take it off the
                  ` closed list and put it back onto the Open list with the new values
                  If AStar_map(newLocation).f > tmpf
                     `_AStar_closed_remove(newLocation)
                     `doIt = 1
                  EndIf
               Else
                  `Check if it's already on the Open List
                  If AStar_map(newLocation).open > 0
                     `If it is, then we compare the values as for the closed list
                     If AStar_map(newLocation).f > tmpf
                        `_AStar_closed_remove(newLocation)
                        doIt = 1
                     EndIf
                  Else
                     doIt = 1
                  EndIf
               EndIf



               If doIt = 1
                  AStar_map(newLocation).parent = location
                  AStar_map(newLocation).parentCount = AStar_map(location).parentCount + 1
                  AStar_map(newLocation).g = tmpg
                  AStar_map(newLocation).h = tmph
                  AStar_map(newLocation).f = tmpf
                  `Penalties for turns
                  If location - AStar_map(location).parent <> i Then AStar_map(newLocation).f = AStar_map(newLocation).f + AStar_penalty_turn
                  If AStar_map(newLocation).open = 0
                     AStar_binary_new(newLocation, 0)
                  Else
                     AStar_binary_new(newLocation, AStar_map(newLocation).open)
                  EndIf

                  If newLocation = goal Then location = goal : Exit

remstart ######################
If debug = 1
Print Str$(newLocation) + ", f = " + Str$(AStar_map(newLocation).f) + ", g = " + Str$(AStar_map(newLocation).g) + ", h = " + Str$(AStar_map(newLocation).h) + ", XPos = " + Str$(((newLocation) MOD AStar_width)) + ", YPos = " + Str$(((newLocation) - ((newLocation) MOD AStar_width)) / AStar_width) + ", Open = " + Str$(AStar_map(newLocation).open)
Sync : Sync
Wait Key
EndIf
remend `######################

               EndIf

            EndIf

         EndIf
      Next i

      `Did we find the goal this time?
      If location = goal Then Exit


      `Left and Right of current Node
      For i = -1 To 1 Step 2

remstart ######################
If debug = 1
If location + i > AStar_width * AStar_height - 1
   Exit Prompt "Urm... Location (" + Str$(location + i) + ") is too big, wtf? On Loop Number " + Str$(loopNum), "Whoops!"
   End
EndIf
EndIf
remend `######################

         newLocation = location + i

         If AStar_map(newLocation).traversable = 0


            `Reset the value
            doIt = 0

            `Work out the F, G, H values
            tmpg = AStar_map(location).g + AStar_g_perp
            tmph = AStar_get_heuristic(((newLocation) MOD AStar_width) , ((newLocation) - ((newLocation) MOD AStar_width)) / AStar_width , x2 , y2 )
            tmpf = tmpg + tmph

            `Need a check for if it's on the closed list already
            If AStar_map(newLocation).closed > 0
               `If it is on the closed list, we need to check if the new values
               ` Are better than those previously in it. If so, take it off the
               ` closed list and put it back onto the Open list with the new values
               If AStar_map(newLocation).f > tmpf
                  `_AStar_closed_remove(newLocation)
                  `doIt = 1
               EndIf
            Else
               `Check if it's already on the Open List
               If AStar_map(newLocation).open > 0
                  `If it is, then we compare the values as for the closed list
                  If AStar_map(newLocation).f > tmpf
                     `_AStar_closed_remove(newLocation)
                     doIt = 1
                  EndIf
               Else
                  doIt = 1
               EndIf
            EndIf



            If doIt = 1
               AStar_map(newLocation).parent = location
               AStar_map(newLocation).parentCount = AStar_map(location).parentCount + 1
               AStar_map(newLocation).g = tmpg
               AStar_map(newLocation).h = tmph
               AStar_map(newLocation).f = tmpf
               `Penalties for turns
               If location - AStar_map(location).parent <> i Then AStar_map(newLocation).f = AStar_map(newLocation).f + AStar_penalty_turn
               If AStar_map(newLocation).open = 0
                  AStar_binary_new(newLocation, 0)
               Else
                  AStar_binary_new(newLocation, AStar_map(newLocation).open)
               EndIf

remstart ######################
If debug = 1
Print Str$(newLocation) + ", f = " + Str$(AStar_map(newLocation).f) + ", g = " + Str$(AStar_map(newLocation).g) + ", h = " + Str$(AStar_map(newLocation).h) + ", XPos = " + Str$(((newLocation) MOD AStar_width)) + ", YPos = " + Str$(((newLocation) - ((newLocation) MOD AStar_width)) / AStar_width) + ", Open = " + Str$(AStar_map(newLocation).open)
Sync : Sync
Wait Key
EndIf
remend `######################

               If newLocation = goal Then location = goal : Exit
            EndIf

         EndIf
      Next i

      `Did we find the goal this time?
      If location = goal Then Exit

      `Row below current node
      For i = AStar_off2 To AStar_off2 + 2

remstart ######################
If debug = 1
If location + i > AStar_width * AStar_height - 1
   Exit Prompt "Urm... Location (" + Str$(location + i) + ") is too big, wtf? On Loop Number " + Str$(loopNum), "Whoops!"
   End
EndIf
EndIf
remend `######################

         newLocation = location + i

         If AStar_map(newLocation).traversable = 0

            `Reset the value
            doIt = 0
            masterCut = 0

            `Work out the F, G, H values
            If i - AStar_off2 = 1
               tmpg = AStar_map(location).g + AStar_g_perp
            Else
               tmpg = AStar_map(location).g + AStar_g

               `Can we use it, though? Does it cut a corner?
               If AStar_diag_Pass = 0
                  If i - AStar_off2 = 0
                     If AStar_map(location - 1).traversable = 1 Or AStar_map(location + AStar_off2 + 1).traversable = 1 Then masterCut = 1
                  Else
                     If AStar_map(location + 1).traversable = 1 Or AStar_map(location + AStar_off2 + 1).traversable = 1 Then masterCut = 1
                  EndIf
               EndIf

            EndIf

            If masterCut = 0

               tmph = AStar_get_heuristic(((newLocation) MOD AStar_width) , ((newLocation) - ((newLocation) MOD AStar_width)) / AStar_width , x2 , y2 )

               tmpf = tmpg + tmph

               `Need a check for if it's on the closed list already
               If AStar_map(newLocation).closed > 0
                  `If it is on the closed list, we need to check if the new values
                  ` Are better than those previously in it. If so, take it off the
                  ` closed list and put it back onto the Open list with the new values
                  If AStar_map(newLocation).f > tmpf
                     `_AStar_closed_remove(newLocation)
                     `doIt = 1
                  EndIf
               Else
                  `Check if it's already on the Open List
                  If AStar_map(newLocation).open > 0
                     `If it is, then we compare the values as for the closed list
                     If AStar_map(newLocation).f > tmpf
                        `_AStar_closed_remove(newLocation)
                        doIt = 1
                     EndIf
                  Else
                     doIt = 1
                  EndIf
               EndIf



               If doIt = 1
                  AStar_map(newLocation).parent = location
                  AStar_map(newLocation).parentCount = AStar_map(location).parentCount + 1
                  AStar_map(newLocation).g = tmpg
                  AStar_map(newLocation).h = tmph
                  AStar_map(newLocation).f = tmpf
                  `Penalties for turns
                  If location - AStar_map(location).parent <> i Then AStar_map(newLocation).f = AStar_map(newLocation).f + AStar_penalty_turn
                  If AStar_map(newLocation).open = 0
                     AStar_binary_new(newLocation, 0)
                  Else
                     AStar_binary_new(newLocation, AStar_map(newLocation).open)
                  EndIf

remstart ######################
If debug = 1
Print Str$(newLocation) + ", f = " + Str$(AStar_map(newLocation).f) + ", g = " + Str$(AStar_map(newLocation).g) + ", h = " + Str$(AStar_map(newLocation).h) + ", XPos = " + Str$(((newLocation) MOD AStar_width)) + ", YPos = " + Str$(((newLocation) - ((newLocation) MOD AStar_width)) / AStar_width) + ", Open = " + Str$(AStar_map(newLocation).open)
Sync : Sync
Wait Key
EndIf
remend `######################

                  If newLocation = goal Then location = goal : Exit

               EndIf

            EndIf

         EndIf
      Next i

      `Did we find the goal this time?
      If location = goal Then Exit


remstart ######################
If debug = 1
Ink 0,0
Box Screen Width () - 80, 0, Screen Width(), Screen Height()
Ink RGB(255,255,255),0
Text Screen Width() - 40, 0, "(" + Str$(AStar_total_Open) + ")"
For i = 1 To AStar_total_Open
   Text Screen Width() - 40, i * 20, Str$(AStar_Open(i)) + "/" + Str$(AStar_map(AStar_Open(i)).open)
Next i
Text Screen Width() - 85, 0, "(" + Str$(AStar_total_Closed) + ")"
For i = 1 To AStar_total_Closed
   Text Screen Width() - 80, i * 20, Str$(AStar_Closed(i)) + "/" + Str$(AStar_map(AStar_Closed(i)).closed)
Next i
Sync : Sync
Wait Key
EndIf
remend `######################

      `Put this parent onto the Closed Heap
      _AStar_closed_add(location)

      `Now, find our next Parent node by grabbing the lowest from the Open list
      location = AStar_binary_get()

remstart ######################
If debug = 1
Ink 0,0
Box Screen Width () - 80, 0, Screen Width(), Screen Height()
Ink RGB(255,255,255),0
Text Screen Width() - 40, 0, "(" + Str$(AStar_total_Open) + ")"
For i = 1 To AStar_total_Open
   Text Screen Width() - 40, i * 20, Str$(AStar_Open(i)) + "/" + Str$(AStar_map(AStar_Open(i)).open)
Next i
Text Screen Width() - 85, 0, "(" + Str$(AStar_total_Closed) + ")"
For i = 1 To AStar_total_Closed
   Text Screen Width() - 80, i * 20, Str$(AStar_Closed(i)) + "/" + Str$(AStar_map(AStar_Closed(i)).closed)
Next i
Sync : Sync
Wait Key
EndIf
remend `######################

   Until (location = goal) Or (AStar_total_Open = 0)


   `Ok, so we've found the final child, and as such we just track back till we get to our parent
   `[No Nodes Ex. Start Node Inc. End Node]
   `For each Node:
   `  Integer [XPos in Map]
   `  Integer [YPos in Map]


   result = Make Memory(4 + (8 * AStar_map(location).parentCount))

remstart ######################
If debug = 1
Cls
Text 0,0,"Total Tiles Passed: " + Str$(AStar_map(location).parentCount)

Sync : Sync
Wait Key
EndIf
remend `######################

   tmpMem = result

   `The header
   (*tmpMem) = AStar_map(location).parentCount : Inc tmpMem, 4

   If AStar_map(location).parentCount > 0
      `The X/Y Info
remstart
      Inc tmpMem, (8 * AStar_map(location).parentCount)

      Repeat
         Dec tmpMem, 8
         (*tmpMem) = (location MOD AStar_width) : Inc tmpMem, 4
         (*tmpMem) = (location - (location MOD AStar_width)) / AStar_width : Dec tmpMem, 4
         location = AStar_map(location).parent
      `Keep going till the next parent is the start square, we don't need that one
      Until location = y1 * AStar_width + x1
remend
      newLocation = location
      Repeat
         (*tmpMem) = (newLocation MOD AStar_width) : Inc tmpMem, 4
         (*tmpMem) = (newLocation - (newLocation MOD AStar_width)) / AStar_width : Inc tmpMem, 4
         newLocation = AStar_map(newLocation).parent
      `Keep going till the next parent is the start square, we don't need that one
      Until newLocation = y1 * AStar_width + x1

   EndIf


   `Clean up so there's no conflict's next time we try to run it
   For i = 1 To AStar_total_Open
      AStar_map(AStar_Open(i)).f = 0
      AStar_map(AStar_Open(i)).g = 0
      AStar_map(AStar_Open(i)).h = 0
      AStar_map(AStar_Open(i)).parentCount = 0
      AStar_map(AStar_Open(i)).open = 0
      AStar_Open(i) = 0
   Next i

   For i = 1 To AStar_total_Closed
      AStar_map(AStar_Closed(i)).f = 0
      AStar_map(AStar_Closed(i)).g = 0
      AStar_map(AStar_Closed(i)).h = 0
      AStar_map(AStar_Closed(i)).parentCount = 0
      AStar_map(AStar_Closed(i)).closed = 0
      AStar_Closed(i) = 0
   Next i

   AStar_total_Closed = 0
   AStar_total_Open = 0

EndFunction result



Function _AStar_closed_remove(index As Integer)

   AStar_map(AStar_Closed(index)).closed = 0
   AStar_map(AStar_Closed(index)).open = 0
   AStar_Closed(index) = 0

   If AStar_total_Closed < 0
      If File Exist("Error.txt") Then Delete File "Error.txt"
      Open To Write 1, "Error.txt"
      Write String 1, "It's below BEFORE (" + Str$(AStar_total_Closed) + ") decrementing and doing its stuff"
      Close File 1
      End
   EndIf

   Dec AStar_total_Closed, 1

   If index <= AStar_total_Closed
      For i = index To AStar_total_Closed
         AStar_Closed(i) = AStar_Closed(i + 1)
         AStar_map(AStar_Closed(i)).closed = i
      Next i
   EndIf

   If AStar_total_Closed < 0
      If File Exist("Error.txt") Then Delete File "Error.txt"
      Open To Write 1, "Error.txt"
      Write String 1, "It's below AFTER (" + Str$(AStar_total_Closed) + ") decrementing and doing its stuff"
      Close File 1
      End
   EndIf

EndFunction



Function _AStar_closed_add(value As Integer)

   Inc AStar_total_Closed

remstart ######################
If debug = 1
If (AStar_total_Closed > Array Count(AStar_Closed(0))) Or (AStar_total_Closed < 0) Then Exit Prompt "Total Closed = " + Str$(AStar_total_Closed) + ", Array size = " + Str$(Array Count(AStar_Closed(0))), "Not Good!" : End
EndIf
remend `######################

   AStar_Closed(AStar_total_Closed) = value
   AStar_map(value).closed = AStar_total_Closed
   AStar_map(value).open = 0

EndFunction


`reorderIndex should be zero if it's a new item,
` if it's an already existing item, it should be its index
Function AStar_binary_new(value As Integer, reorderIndex As Integer)

   Local count As Integer
   Local temp As Integer

   `Keep track of where in the list it has bubbled to so far
   If reorderIndex > 0
      count = reorderIndex
      `AStar_Open(count) = value
   Else
      `Reflect the new size
      Inc AStar_total_Open

remstart ######################
If debug = 1
If AStar_total_Open <= 0 Or AStar_total_Open > AStar_width * AStar_height
   If File Exist("Error.txt") Then Delete File "Error.txt"
   Open To Write 1, "Error.txt"
   For i = 0 To AStar_total_Closed
      Write String 1, Str$(AStar_Closed(i))
   Next i
   Close File 1
   Exit Prompt "Urm... AStar_total_Open (" + Str$(AStar_total_Open) + ") is too low, wtf? Info saved to Error.txt", "Whoops!"
   End
EndIf
EndIf
remend `######################


      `Add the new value at the 'end' of the list
      AStar_Open(AStar_total_Open) = value

      count = AStar_total_Open
   EndIf

   `Repeat until it reaches the top of the list
   ` ( Or EXITs as in the 'ELSE' )
   While count >= 4

      `If This one is less than its parent, then swap them
      If AStar_map(AStar_Open(count)).f <= AStar_map(AStar_Open(Int(count / 2))).f

remstart ######################
If AStar_Open(Int(count / 2)) = 0 Or AStar_Open(count) = 0 Or count < 4
   Sync : Sync
   Wait Key
   Exit Prompt "U-oh!, Value = " + Str$(value) + " No. " + Str$(Int(count / 2)) + " = " + Str$(AStar_Open(Int(count / 2))) + " No. " + Str$(count) + " = " + Str$(AStar_Open(count)) + " reorderIndex = " + Str$(reorderIndex), ":("
   End
EndIf
remend `######################

         `Do the swapping
         temp = AStar_Open(Int(count / 2))
         AStar_Open(Int(count / 2)) = AStar_Open(count)
         AStar_Open(count) = temp

         AStar_map(AStar_Open(count)).open = count
         AStar_map(AStar_Open(Int(count / 2))).open = Int(count / 2)

         `Now we're at the 'parent's location
         count = Int(count / 2)
      Else
         `Nope, not lower, it's as high as it can go, so exit the loop
         Exit
      EndIf

   EndWhile

   `set the tracking variable
   AStar_map(AStar_Open(count)).open = count


EndFunction




Function AStar_binary_get()


remstart ######################
If debug = 1
If AStar_total_Open <= 0 Or AStar_total_Open > AStar_width * AStar_height
   If File Exist("Error.txt") Then Delete File "Error.txt"
   Open To Write 1, "Error.txt"
   For i = 0 To AStar_total_Closed
      Write String 1, Str$(AStar_Closed(i))
   Next i
   Close File 1
   Exit Prompt "Urm... AStar_total_Open (" + Str$(AStar_total_Open) + ") is too low, wtf? Info saved to Error.txt", "Whoops!"
   End
EndIf
EndIf
remend `######################


   Local result As Integer

   Local temp As Integer

   Local v As Integer
   Local u As Integer

   `Reset the top-most's Open track to 0 as it is about to be put on the Closed List
   AStar_map(AStar_Open(1)).open = 0


   `Now, start the removal process so that our heap isn't totally screwed up
   `Move the last-most to the front
   AStar_Open(1) = AStar_Open(AStar_total_Open)
   AStar_map(AStar_Open(1)).open = 1

   AStar_Open(AStar_total_Open) = 0

   `Reflect the removal of one item
   Dec AStar_total_Open

   `Initialize the starting place
   v = 1

   `Repeat until we want to exit
   Do
      u = v

      `If both the children exist ( ie, it CAN go further down the list )
      If (2*u) + 1 <= AStar_total_Open

         `Select the lowest of the two children ( Notice the use of u and v )
         If AStar_map(AStar_Open(u)).f >= AStar_map(AStar_Open(2*u)).f Then v = 2*u
         If AStar_map(AStar_Open(v)).f >= AStar_map(AStar_Open((2*u) + 1)).f Then v = (2*u) + 1

      Else
         If (2*u) <= AStar_total_Open
            `Check if the cost is greater than the child
            If AStar_map(AStar_Open(u)).f >= AStar_map(AStar_Open(2*u)).f Then v = 2*u
         EndIf
      EndIf

      `Now, if we've found a child smaller than the parent, swap them
      If u <> v
         temp = AStar_Open(u)
         AStar_Open(u) = AStar_Open(v)
         AStar_Open(v) = temp
         `And swap the tracking variables also
         AStar_map(AStar_Open(u)).open = u
         AStar_map(AStar_Open(v)).open = v
      Else
         `Whoops, the parent is in the right spot, let's exit!
         Exit
      EndIf
   Loop

   `Get the top-most from the heap
   result = AStar_Open(1)

EndFunction result



Function AStar_get_heuristic(x1 As Integer, y1 As Integer, x2 As Integer, y2 As Integer)

   result As Integer
   dx As Integer
   dy As Integer
   min As Integer

   dx = Abs(x2 - x1)
   dy = Abs(y2 - y1)

   If dx < dy Then min = dx Else min = dy

   `diagdistance*min(|dx|,|dy|) + orthodistance*||dx|-|dy||

   result = (AStar_g * min) + (AStar_g_perp * Abs(dx - dy))

`   result = (dx + dy) * AStar_g_perp

EndFunction result



remstart
Function _AStar_flood_fill(x1 As Integer, y1 As Integer)

   Local totalFilled As Integer
   Local location As Integer

   Dim AStar_flood(AStar_width * AStar_height) As floodfill

   Inc totalFilled
   AStar_flood(totalFilled).location = y1 * AStar_width + x1
   AStar_flood(totalFilled).accessable = 1

   For m = 1 To totalFilled

      location = AStar_flood(m).location

      `Row above current node
      For i = AStar_off1 To AStar_off1 + 2
         If AStar_map(location + i).traversable <> 1 `And NEED SOMETHING THAT CHECKS IF IT'S ALREADY BEEN ADDED!
            Inc totalFilled
            AStar_flood(totalFilled).location = location + i
            AStar_flood(totalFilled).accessable = 1
         EndIf
      Next i

      `Left and Right of current Node
      For i = -1 To 1 Step 2
         If AStar_map(location + i).traversable <> 1
            Inc totalFilled
            AStar_flood(totalFilled).location = location + i
            AStar_flood(totalFilled).accessable = 1
         EndIf
      Next i

      `Row below current node
      For i = AStar_off2 To AStar_off2 + 2
         If AStar_map(location + i).traversable <> 1
            Inc totalFilled
            AStar_flood(totalFilled).location = location + i
            AStar_flood(totalFilled).accessable = 1
         EndIf
      Next i
   Next m

EndFunction
remend

And a sample app:

Sync On : Sync Rate 0 : Randomize Timer()

Set Text Font "Verdana"
Set Text Size 12
Set Text Opaque

`For the A*
Type openclosed
   traversable As Boolean
   parent As Integer
   parentCount As Integer
   open As Integer
   closed As Integer
   f As Integer
   g As Integer
   h As Integer
EndType

Global mapSize As Integer = 60

Global sx As Integer
Global sy As Integer
Global ex As Integer
Global ey As Integer

update As Boolean = 1

tmpInt As Integer

Dim World(mapSize - 1,mapSize - 1) As Integer

_AStar_init(mapSize,mapSize)
_AStar_enable_diagonal_cutting(0)

For y = 0 To mapSize - 1
   For x = 0 To mapSize - 1
      Read tmpInt
      World(x,y) = tmpInt
      If World(x,y) = 1 Then _AStar_set_terrain(x, y, 1)
      If World(x,y) = 2 Then sx = x : sy = y
      If World(x,y) = 3 Then ex = x : ey = y
   Next x
Next y

Global ptrAStar As DWord
Global tmpPtrAStar As DWord

timeStart As Integer
timeEnd As Integer
totalTime As Integer = 0

x1 As Integer
y1 As Integer
x2 As Integer
y2 As Integer

remstart
Repeat
   sx = Rnd(mapSize - 1)
   sy = Rnd(mapSize - 1)
Until World(sx,sy) <> 1
World(sx,sy) = 2

Repeat
   ex = Rnd(mapSize - 1)
   ey = Rnd(mapSize - 1)
Until World(ex,ey) <> 1
World(ex,ey) = 3
remend
`Text 0,0,"Start: " + Str$(sx) + ", " + Str$(sy)
`Text 0,20,"End: " + Str$(ex) + ", " + Str$(ey)

`Sync : Sync
`Wait Key

For i = 0 To 0
   timeStart = Timer()
   ptrAStar = _AStar_find_path(sx, sy, ex, ey)
   timeEnd = Timer()
   totalTime = totalTime + (timeEnd - timeStart)
Next i

For y = 0 To mapSize - 1
   For x = 0 To mapSize - 1
      If World(x,y) = 2 Then Ink RGB(0,200,0), 0
      If World(x,y) = 3 Then Ink RGB(200,0,0), 0
      If World(x,y) = 1 Then Ink RGB(0,0,200), 0
      If World(x,y) = 0 Then Ink 0, 0

Box x * 10, y * 10, (x+1)*10, (y+1)*10

Ink RGB(20,20,20),0
      _box(x * 10, y * 10, (x+1)*10, (y+1)*10)
   Next x
Next y

Ink RGB(255,255,255),0

Do

If MouseClick() = 1 : If keyR = 0 : keyR = 1
   `** On KeyDown **

tmpPtrAStar = ptrAStar
      Inc tmpPtrAStar, 4

tmpInt = (*ptrAStar)

Ink 0,0

If tmpInt > 0
         For i = 0 To (*ptrAStar)
            x1 = (*tmpPtrAStar) * 10 + 4 : Inc tmpPtrAStar, 4
            y1 = (*tmpPtrAStar) * 10 + 4 : Inc tmpPtrAStar, 4
            x2 = x1 + 2
            y2 = y1 + 2

Box x1, y1, x2, y2

Next i
      Else
         Text 650,400,"NO SOLUTION!"
      EndIf

Box sx * 10 + 1, sy * 10 + 1, (sx+1)*10, (sy+1)*10
      Box ex * 10 + 1, ey * 10 + 1, (ex+1)*10, (ey+1)*10

Delete Memory ptrAStar
      totalTime = 0

For i = 0 To 0

World(sx,sy) = 0
         World(ex,ey) = 0

Repeat
            sx = Rnd(mapSize - 1)
            sy = Rnd(mapSize - 1)
         Until World(sx,sy) <> 1
         World(sx,sy) = 2

Repeat
            ex = Rnd(mapSize - 1)
            ey = Rnd(mapSize - 1)
         Until (World(ex,ey) <> 1) And ((ex <> sx) And (ey <> sy))
         World(ex,ey) = 3

timeStart = Timer()
         ptrAStar = _AStar_find_path(sx, sy, ex, ey)
         timeEnd = Timer()
         totalTime = totalTime + (timeEnd - timeStart)
      Next i

update = 1

`** End On Down **
   Else
   `** While KeyHeld **
   `** End Held **
   EndIf : Else : If keyR = 1 : keyR = 0
   `** On KeyUp **
   `** End On Up **
   EndIf : EndIf

If update = 1

tmpPtrAStar = ptrAStar
      Inc tmpPtrAStar, 4

tmpInt = (*ptrAStar)

Ink RGB(0,200,0),0
      Box sx * 10 + 1, sy * 10 + 1, (sx+1)*10, (sy+1)*10
      Ink RGB(200,0,0),0
      Box ex * 10 + 1, ey * 10 + 1, (ex+1)*10, (ey+1)*10

Ink RGB(255,255,255),0

If tmpInt > 0
         For i = 0 To (*ptrAStar)
            x1 = (*tmpPtrAStar) * 10 + 4 : Inc tmpPtrAStar, 4
            y1 = (*tmpPtrAStar) * 10 + 4 : Inc tmpPtrAStar, 4
            x2 = x1 + 2
            y2 = y1 + 2

`Text x1 - 3, y1 - 3, Str$(i)

Box x1, y1, x2, y2

Next i
      Else
         Text 650,400,"NO SOLUTION!"
      EndIf

Text Screen Width() - Text Width("Time Taken: xxxxxxms"), Screen Height() - 20, "Time Taken: " + Str$(totalTime) + "ms  "

update = 0
   EndIf

Text 650,0,"FPS:     "
   Text 650,0,"FPS: " + Str$(Screen FPS())

Sync
Loop

Function _box(x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer)

Line x1,y1,x2,y1
   Line x2,y1,x2,y2
   Line x2,y2,x1,y2
   Line x1,y2,x1,y1

EndFunction

Function _filled_box(x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer, colour As DWord)

`Pixel data is in ABGR order
   pixelPtr As DWord

pixelPtr = Get Pixels Pointer()
   tmpPtr = pixelPtr

For y = y1 To y2
      Inc pixelPtr, Screen Width() * y
      For x = x1 To x2
         Inc pixelPtr, x
         tmpPtr = pixelPtr + 1
         *tmpPtr = RGBB(colour) : Inc tmpPtr, 1
         *tmpPtr = RGBG(colour) : Inc tmpPtr, 1
         *tmpPtr = RGBR(colour)
         Dec pixelPtr, x
      Next x
   Next y

EndFunction

remstart
Data 1,1,1,1,1,1,1
Data 1,0,0,0,0,0,1
Data 1,0,0,1,0,0,1
Data 1,2,0,1,0,3,1
Data 1,0,0,1,0,0,1
Data 1,0,0,1,0,0,1
Data 1,1,1,1,1,1,1
remend

Data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,1
Data 1,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1
Data 1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

+ Code Snippet

Sync On : Sync Rate 0 : Randomize Timer()

Set Text Font "Verdana"
Set Text Size 12
Set Text Opaque


`For the A*
Type openclosed
   traversable As Boolean
   parent As Integer
   parentCount As Integer
   open As Integer
   closed As Integer
   f As Integer
   g As Integer
   h As Integer
EndType


Global mapSize As Integer = 60

Global sx As Integer
Global sy As Integer
Global ex As Integer
Global ey As Integer

update As Boolean = 1

tmpInt As Integer

Dim World(mapSize - 1,mapSize - 1) As Integer

_AStar_init(mapSize,mapSize)
_AStar_enable_diagonal_cutting(0)

For y = 0 To mapSize - 1
   For x = 0 To mapSize - 1
      Read tmpInt
      World(x,y) = tmpInt
      If World(x,y) = 1 Then _AStar_set_terrain(x, y, 1)
      If World(x,y) = 2 Then sx = x : sy = y
      If World(x,y) = 3 Then ex = x : ey = y
   Next x
Next y


Global ptrAStar As DWord
Global tmpPtrAStar As DWord

timeStart As Integer
timeEnd As Integer
totalTime As Integer = 0

x1 As Integer
y1 As Integer
x2 As Integer
y2 As Integer

remstart
Repeat
   sx = Rnd(mapSize - 1)
   sy = Rnd(mapSize - 1)
Until World(sx,sy) <> 1
World(sx,sy) = 2

Repeat
   ex = Rnd(mapSize - 1)
   ey = Rnd(mapSize - 1)
Until World(ex,ey) <> 1
World(ex,ey) = 3
remend
`Text 0,0,"Start: " + Str$(sx) + ", " + Str$(sy)
`Text 0,20,"End: " + Str$(ex) + ", " + Str$(ey)

`Sync : Sync
`Wait Key

For i = 0 To 0
   timeStart = Timer()
   ptrAStar = _AStar_find_path(sx, sy, ex, ey)
   timeEnd = Timer()
   totalTime = totalTime + (timeEnd - timeStart)
Next i


For y = 0 To mapSize - 1
   For x = 0 To mapSize - 1
      If World(x,y) = 2 Then Ink RGB(0,200,0), 0
      If World(x,y) = 3 Then Ink RGB(200,0,0), 0
      If World(x,y) = 1 Then Ink RGB(0,0,200), 0
      If World(x,y) = 0 Then Ink 0, 0

      Box x * 10, y * 10, (x+1)*10, (y+1)*10

      Ink RGB(20,20,20),0
      _box(x * 10, y * 10, (x+1)*10, (y+1)*10)
   Next x
Next y

Ink RGB(255,255,255),0


Do

   If MouseClick() = 1 : If keyR = 0 : keyR = 1
   `** On KeyDown **

      tmpPtrAStar = ptrAStar
      Inc tmpPtrAStar, 4

      tmpInt = (*ptrAStar)

      Ink 0,0

      If tmpInt > 0
         For i = 0 To (*ptrAStar)
            x1 = (*tmpPtrAStar) * 10 + 4 : Inc tmpPtrAStar, 4
            y1 = (*tmpPtrAStar) * 10 + 4 : Inc tmpPtrAStar, 4
            x2 = x1 + 2
            y2 = y1 + 2

            Box x1, y1, x2, y2

         Next i
      Else
         Text 650,400,"NO SOLUTION!"
      EndIf

      Box sx * 10 + 1, sy * 10 + 1, (sx+1)*10, (sy+1)*10
      Box ex * 10 + 1, ey * 10 + 1, (ex+1)*10, (ey+1)*10

      Delete Memory ptrAStar
      totalTime = 0

      For i = 0 To 0

         World(sx,sy) = 0
         World(ex,ey) = 0

         Repeat
            sx = Rnd(mapSize - 1)
            sy = Rnd(mapSize - 1)
         Until World(sx,sy) <> 1
         World(sx,sy) = 2

         Repeat
            ex = Rnd(mapSize - 1)
            ey = Rnd(mapSize - 1)
         Until (World(ex,ey) <> 1) And ((ex <> sx) And (ey <> sy))
         World(ex,ey) = 3

         timeStart = Timer()
         ptrAStar = _AStar_find_path(sx, sy, ex, ey)
         timeEnd = Timer()
         totalTime = totalTime + (timeEnd - timeStart)
      Next i

      update = 1

   `** End On Down **
   Else
   `** While KeyHeld **
   `** End Held **
   EndIf : Else : If keyR = 1 : keyR = 0
   `** On KeyUp **
   `** End On Up **
   EndIf : EndIf


   If update = 1

      tmpPtrAStar = ptrAStar
      Inc tmpPtrAStar, 4

      tmpInt = (*ptrAStar)

      Ink RGB(0,200,0),0
      Box sx * 10 + 1, sy * 10 + 1, (sx+1)*10, (sy+1)*10
      Ink RGB(200,0,0),0
      Box ex * 10 + 1, ey * 10 + 1, (ex+1)*10, (ey+1)*10

      Ink RGB(255,255,255),0

      If tmpInt > 0
         For i = 0 To (*ptrAStar)
            x1 = (*tmpPtrAStar) * 10 + 4 : Inc tmpPtrAStar, 4
            y1 = (*tmpPtrAStar) * 10 + 4 : Inc tmpPtrAStar, 4
            x2 = x1 + 2
            y2 = y1 + 2

            `Text x1 - 3, y1 - 3, Str$(i)

            Box x1, y1, x2, y2

         Next i
      Else
         Text 650,400,"NO SOLUTION!"
      EndIf

      Text Screen Width() - Text Width("Time Taken: xxxxxxms"), Screen Height() - 20, "Time Taken: " + Str$(totalTime) + "ms  "

      update = 0
   EndIf

   Text 650,0,"FPS:     "
   Text 650,0,"FPS: " + Str$(Screen FPS())

Sync
Loop



Function _box(x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer)

   Line x1,y1,x2,y1
   Line x2,y1,x2,y2
   Line x2,y2,x1,y2
   Line x1,y2,x1,y1

EndFunction



Function _filled_box(x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer, colour As DWord)

   `Pixel data is in ABGR order
   pixelPtr As DWord

   pixelPtr = Get Pixels Pointer()
   tmpPtr = pixelPtr

   For y = y1 To y2
      Inc pixelPtr, Screen Width() * y
      For x = x1 To x2
         Inc pixelPtr, x
         tmpPtr = pixelPtr + 1
         *tmpPtr = RGBB(colour) : Inc tmpPtr, 1
         *tmpPtr = RGBG(colour) : Inc tmpPtr, 1
         *tmpPtr = RGBR(colour)
         Dec pixelPtr, x
      Next x
   Next y

EndFunction


remstart
Data 1,1,1,1,1,1,1
Data 1,0,0,0,0,0,1
Data 1,0,0,1,0,0,1
Data 1,2,0,1,0,3,1
Data 1,0,0,1,0,0,1
Data 1,0,0,1,0,0,1
Data 1,1,1,1,1,1,1
remend


Data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,1
Data 1,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1
Data 1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
Data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

Of course, you'll have to copy+paste the functions into the bottom of that example, or include them in a seperate file...

Team EOD :: All-Round Nice Guy
Want Better dbHelp Files?

Back to top

Profile PM Email Website

Fallout

22

Years of Service

User Offline

Joined: 1st Sep 2002

Location: Basingstoke, England

Posted: 23rd Feb 2006 01:43

Link

Woah, that's a monster!

I won't be using A* because my system is not tile based, but that's still a damn handy piece of code to have. Very nice of you to chuck it up!

Back to top

Profile PM

Jess T

Retired Moderator

21

Years of Service

User Offline

Joined: 20th Sep 2003

Location: Over There... Kablam!

Posted: 23rd Feb 2006 03:14

Link

Ah well, no worries.

Stick it away somewhere, and one day you may be able to use it

Team EOD :: All-Round Nice Guy
Want Better dbHelp Files?

Back to top

Profile PM Email Website

Fallout

22

Years of Service

User Offline

Joined: 1st Sep 2002

Location: Basingstoke, England

Posted: 23rd Feb 2006 10:30

Link

No doubt mate! I'm bound to have use for it in the future, and it looks well documented and put together. Nice one.

Back to top

Profile PM

Sorry your browser is not supported!

Geek Culture / Alternatives to A*?

Attachments