Jump to content


Photo

PATHFINDER 0.4 - A*Algorythm (A-Star Pathfinding ) + Editor


  • Please log in to reply
13 replies to this topic

#1 IsNull

IsNull
  • Fellows
  • 990 posts

Posted 02 January 2009 - 05:29 PM

Hi folks,

I've created a implementation of the A*Algorythm.

Original German Posting:
:arrow: http://forum.securit...c.php?f=2&t=155

translation by translater :)

Hey, i´ve associated now the A* Path find Algorythm & the Leveleditor to 1 project, so i can present now the PATHFINDER. :D


With Pathfinder you can create maps (labyrinth) and mark one field as player and another field as target. The A* Algorythm find then the optimal way to the target. After this calculation, the Player is "animated" and runs through the labyrinth to the target. :)

DOWNLOAD latest Release

Thats a screen of the Editor Mode:

Posted Image



Instructions:
Test a map:
1. Go to MAP --> Open MAP and choose a map (there are some default maps)
The MAP will be loaded shortly.
3. Now you can start pathfinding with --> Astar --> WALK!

Create a map:
* Press the Create button to create a new map. [.create]. The numbers left to the button shows the dimensions of the field.
* maps can be saved/loaded with the <<Map/Export MAP>> or <<Map/Open MAP>> . There are also some example maps in the download package. Just click open map and choose one!
* maps can be edited, when you choose the "Brush" (i.e. WALL UD) for the red wall, and then right in the map drag the left mouse button you can paint. The right mouse button is associated with the [walkable]-Brush button, so you can delete the walls more quickly.


Changelog:

EDIT 2 [17.01.2009]: Some bugfixes in pathfinder.ahk. Better comfort while saving maps.

EDIT 2 [15.01.2009]: Updated Script with Lexicos improved A*-Algo. - Thanks again ;)

EDIT 1: translation updated.

#2 IsNull

IsNull
  • Fellows
  • 990 posts

Posted 08 January 2009 - 07:17 AM

[UPDATE] ver 0.2
Filepath problem fixed
About menue fixed

#3 Translater

Translater
  • Guests

Posted 08 January 2009 - 12:53 PM

Hey, i´ve associated now the A* Path find Algorythm & the Leveleditor to 1 project, so i can present now the PATHFINDER. :D


With Pathfinder you can create maps (labyrinth) and mark one field as player and another field as target. The A* Algorythm find then the optimal way to the end, then will the Player be "animated" und runs through the labyrinth to the end.

DOWNLOAD latest Release

Thats a screen of the Editor Mode:

Posted Image



instructions:
Create a map
* Press the Create button to create a new map. [.create]. The numbers left to the button shows the dimensions of the field.
* maps can be saved with the <> or <> . There are also some example maps in the download package. Just click open map and choose one!
* maps can be changed , when you choose the "Brush" (i.e. WALL UD) for the red wall, and then right in the map drag the left mouse button you can paint. The right mouse button is associated with the [walkable]-Brush button, so you can delete the walls more quickly.

Testing a map
* First you must load a map. If you´ve created a map, you must save it before.
* Now just choose <> from the menu, and the path will be calculated and animated displayed

:D

#4 IsNull

IsNull
  • Fellows
  • 990 posts

Posted 10 January 2009 - 02:37 PM

@Translater: thanks, i've updatet the initial posting. :)

#5 Laszlo

Laszlo
  • Fellows
  • 4713 posts

Posted 11 January 2009 - 05:33 AM

Nice! It works fast for small labyrinths, but the one I tried, of size 40x40, with a large empty area, takes a minute to solve in my i7 big PC. I think the straightforward implementation of Dijkstra's algorithm would finish in a few seconds. (The slowest seems to be if the player is in a corner, the target boxed in the diagonally opposite corner. The script took almost 2 minutes to tell that there was no connecting path.)

#6 IsNull

IsNull
  • Fellows
  • 990 posts

Posted 11 January 2009 - 10:41 AM

thanks for your reply, Laszlo :)

Nice! It works fast for small labyrinths, but the one I tried, of size 40x40, with a large empty area, takes a minute to solve in my i7 big PC. I think the straightforward implementation of Dijkstra's algorithm would finish in a few seconds. (The slowest seems to be if the player is in a corner, the target boxed in the diagonally opposite corner. The script took almost 2 minutes to tell that there was no connecting path.)

Youre right, it's slow in bigger levels.


Dijkstra's algorithm is the same as A*, exept, that there is no "Heuristic". So, the Path search will expand in all directions on the same time. Maby, this would be faster in cases of impasses in front of the target - cause the algorythm will be confused. On the other hand, A* Algo will find out very fast out of impases, cause every field will be analyzed only once.

I will implement it in c++ and export it as function, so it will be much faster.

btw;
:arrow: <!-- m -->http://www.policyalm...tarTutorial.htm<!-- m -->

#7 Lexikos

Lexikos
  • Administrators
  • 8832 posts

Posted 13 January 2009 - 12:59 PM

Very interesting.

I've made a number of improvements. Old code is in darkred, new or changed code is in indigo. Most indigo should have a "Lexikos" comment explaining it.

AStar.ahk
#Include, %a_scriptdir%\INCLUDE\A_Array.ahk

;######################## DEMO #####################################
/*******************
Legende:
1   =   Player
X   =   WALL
T   =   Target
********************

level=
(
XXXXXXXXXX
XT       X
XXXXXX   X
X        X
X  X  XXXX
X  X  X 1X
X  X  X  X
X XXX X  X
X  X  X  X
X  X  X  X
X  X  X  X
X  XXXXX X
X        X
X XXX    X
XXXXXXXXXX
)

LOAD_leveL(level)
FieldCNT := GameH * GameW
msgbox % astar()
return
;###################################################################
*/

/*****************************************************************
A* (A Star) Algorythm

coded by IsNull 01.01.2009
------------------------------------------------------------------
Searches a path and will find the optimal one.
Returns a string with the path, or 0 if no path exists.
_
http://www.policyalmanac.org/games/aStarTutorial_de.html
******************************************************************
*/
astar_ver := "0.2 ALPHA"
SetBatchLines, -1
astar(){
global
   rounds := 0
   ;------------- creates emtpy array with n places -------
   ;coz A_Array has got a problem writing into empty containers
[color=darkred];    Loop, % FieldCNT[/color]
[color=darkred];    {[/color]
[color=darkred];       A_Put(AS_fVALUE_Field,x := 0)[/color]
[color=darkred];       A_Put(AS_COST_Field,x := 0)[/color]
[color=darkred];    }[/color]
   ; Lexikos: Initialize two arrays of UINT, with length=FieldCNT and init to 0.
   [color=indigo]VarSetCapacity(AS_fVALUE_Field, FieldCNT*4, 0)
   VarSetCapacity(AS_COST_Field, FieldCNT*4, 0)[/color]
   ;------------------------------------------------------

   FeldNr := A_Get(AS_OPENLIST, 1)              ; Feldnummer holen
[color=darkred];    A_Put(AS_COST_Field,x := 0,FeldNr)           ; Kosten für Startfeld = 0[/color]
   ; Lexikos: Above not necessary since already 0.
   
   Loop
   {
      FeldNr := GetNextField()                  ; Gibt das nächste Feld zurück
      If(!FeldNr){
         break                                  ; Es existiert kein Pfad
      }
      path := AddNeightboor(FeldNr)
      IF(path != 0){   ; Nachbarn in Openlist speichern
         break                                  ; Pfad wurde gefunden
      }
      ++rounds 
   }
   ;Pfadsuche beendet. Erfolgreich oder nicht erfolgreich.
   ;msgbox % "Habe " rounds " Runden benötig um den Pfad zu finden."
   return, path
} ;*************************************************************

/****************************************************************
Diese Funktion sucht alle Nachbarn (des ausgang Feldes und fügt sie in die Openlist hinzu.)
Diese müssen aus der anderen Liste entfernt werden!

*****************************************************************
*/
AddNeightboor(FieldNR){
global

[color=darkred];    c := A_Get(AS_FIELD_COORD,FieldNR)    ;Koordinaten des Feldes holen[/color]
[color=darkred];    pos := RegExMatch(c,"([0-9]*)\|([0-9]*)",out)[/color]
[color=darkred];    If(!pos){[/color]
[color=darkred];       msgbox,16,Error, % "In '" c "' konnte keine Koordinaten gefunden werden!`nFeldnummer: [" FieldNR "]"[/color]
[color=darkred];       exitapp[/color]
[color=darkred];    }[/color]
   ; Lexikos: Instead of above, derive the coords from the field number.
   [color=indigo]out1 := Mod(FieldNR-1,GameW)+1
   out2 := (FieldNR-1)//GameW+1[/color]
   
   ;es gibt vier angrenzende Felder, somit :
   a1x := out1, a1y := out2 + 1
   a2x := out1 + 1, a2y := out2
   a3x := out1 - 1, a3y := out2
   a4x := out1, a4y := out2 - 1
   
   ;FeldinHalt bestimmen:
   Loop, 4
   {

      If(a%a_index%x > GameW) OR (a%a_index%y > GameH) OR (a%a_index%x < 1) OR (a%a_index%y < 1){
         ;msgbox % "Koord(" a%a_index%x "|" a%a_index%y ") Verworfen! Out of Levelrange`nMax Koord: (" GameW "|"  GameH ")"
         continue
      }
      
      tmp := GETField(a%a_index%x,a%a_index%y)
      FNr := GetFieldNr(a%a_index%x,a%a_index%y)
      
      ; Lexikos: Checking for "X" here avoids unnecessarily searching the AS_ClosedList array,
      ;          and also avoids the need to put any "X" into the array. The less items we put
      ;          into the array, the faster it is to search through.
      [color=indigo]if tmp = X
         continue[/color]
      
[color=darkred];       If(IsValinArray(AS_ClosedList,FNr) OR IsValinArray(AS_OPENLIST,FNr)){[/color]
         ;msgbox % "Koord(" a%a_index%x "|" a%a_index%y ") Verworfen! Nicht in Liste"
      ;*Lexikos: Check "opened" status of node instead of searching list.
      [color=indigo]if NumGet(AS_opened, FNr-1, "char")[/color]
         continue   ;Dieses Feld wird nicht analysiert
[color=darkred];       }[/color]
      ;Es ist ein begehbares Feld, welches noch nicht verwendet wurde.
      A_Put(AS_OPENLIST, FNr)                       ;füge es der openlist hinzu
      
      ;*Lexikos: Set "opened" status of this field.
      [color=indigo]NumPut(1, AS_opened, FNr-1, "char")[/color]
      
      ;################# FKosten berechnen: ################
      ;G - Weg vom Start bis hier hin berechnen

[color=darkred];       G_KOSTEN := A_Get(AS_COST_Field,FieldNR) + 1    ;Weg Kosten(G) berechnen für dieses Feld[/color]
      ; Lexikos: Get value from UINT array at index FieldNR.
      ;          (-1 for 0-based offset, *4 because 4 bytes per UINT)
      [color=indigo]G_KOSTEN := 1 + NumGet(AS_COST_Field, (FieldNR-1)*4)[/color]

[color=darkred];       A_Put(AS_COST_Field,G_KOSTEN,FNr)               ;an des Feldes Die Kosten hinschreiben[/color]
      ; Lexikos: Put value into UINT array at index FNr.
      [color=indigo]NumPut(G_KOSTEN, AS_COST_Field, (FNr-1)*4)[/color]

      ;--------------------------------
      ;H - Weg von aktuellem Feld bis zum Ziel schätzen
      active_x  := a%a_index%x
      active_y  := a%a_index%y
      H_Kosten  := abs(t1x - active_x) + abs(t1y - active_y)    ;x- sowie y-unterschied zusammenzählen.
      ;F-Wert
      F_KOSTEN  := G_KOSTEN + H_Kosten

[color=darkred];       A_Put(AS_fVALUE_Field,F_KOSTEN,FNr)                       ;F-Wert schreiben[/color]
      ; Lexikos: Put value into UINT array at index FNr.
      [color=indigo]NumPut(F_KOSTEN, AS_fVALUE_Field, (FNr-1)*4)[/color]
      
      ;#####################################################
[color=darkred];       AS_parent_%FNr% := FieldNR                    ;das Vorgänger Feld dieses merken[/color]
      ; Lexikos: Put value into UINT array at index FNr.
      [color=indigo]NumPut(FieldNR, AS_parent, (FNr-1)*4)[/color]
      
      ;---------------------------------------------------------------------------
      
      If((a%a_index%x = t1x) AND (a%a_index%y = t1y)){  ;wenn die Koordinaten des nächsten Feldes gleich die dem Ziel sind
         return, ReGoPath(GetFieldNr(t1x,t1y))          ;ist der Pfad gefunden ;)
      }
      
   }    
   DeleteValInArray(AS_OPENLIST,FieldNR)            ;Diese Nummer aus der Openlist entfernen
[color=darkred];    A_Put(AS_ClosedList, FieldNR)                    ;und bei der ClosedLit hinzufügen[/color]
   ;*Lexikos: AS_ClosedList no longer necessary.
   return, 0
}
;****************************************************************

/****************************************************************
Gibt das Nächste Feld zurück.
*****************************************************************
*/
GetNextField(){
;global
local min_val, min_fnr
   min_val  := -1
   If(A_Count(AS_OPENLIST) = 0){
      return, 0
   }
   
   Loop, % A_Count(AS_OPENLIST)
   {
      FNr       := A_Get(AS_OPENLIST,a_index)

[color=darkred];       FValue    := A_Get(AS_fVALUE_Field,FNr)[/color]
      ; Lexikos: Get value from UINT array at index FNr.
      [color=indigo]FValue := NumGet(AS_fVALUE_Field, (FNr-1)*4)[/color]
      
      IF (min_val = -1) OR (FValue < min_val){
         min_val := FValue
         ; Lexikos: Avoid the extra unnecessary loop by recording FNr.
         [color=indigo]min_fnr := FNr[/color]
      }
   }
   ;min_val ist die kleinste FValue
   ;nochmals loopen und bei der ersten min_val das Feld zurückgeben
[color=darkred];    Loop, % A_Count(AS_OPENLIST)[/color]
[color=darkred];    {[/color]
[color=darkred];       FNr       := A_Get(AS_OPENLIST,a_index)[/color]
[color=darkred];       FValue    := A_Get(AS_fVALUE_Field,FNr)[/color]
[color=darkred];       IF (FValue = min_val){[/color]
[color=darkred];          return, FNr[/color]
[color=darkred];       }[/color]
[color=darkred];    }[/color]
   return min_fnr
} ;**************************************************************

/****************************************************************
Geht einen Pfad zurück
*****************************************************************
*/
ReGoPath(FieldNr){
global
   THEPATH  := ""
   START_FIELD := GetFieldNr(p1x,p1y)
   THEPATH  := "{" FieldNr "}"
   THEPATH2 :=
   Loop
   {
      parent_FNr := trim_num(get_parent(FieldNr))
      
[color=darkred];       cc := A_Get(AS_FIELD_COORD,FieldNR)       ;Koordinaten des Feldes holen[/color]
[color=darkred];       cp := A_Get(AS_FIELD_COORD,parent_FNr)    ;Koordinaten des Feldes holen[/color]
[color=darkred];       RegExMatch(cc,"([0-9]*)\|([0-9]*)",ccout)[/color]
[color=darkred];       RegExMatch(cp,"([0-9]*)\|([0-9]*)",cpout)[/color]
      ; Lexikos: Instead of above, derive the coords from the field number.
      [color=indigo]ccout1 := Mod(FieldNR-1,GameW)+1
      ccout2 := (FieldNR-1)//GameW+1
      cpout1 := Mod(parent_FNr-1,GameW)+1
      cpout2 := (parent_FNr-1)//GameW+1[/color]
      
      deltax    := ccout1 - cpout1
      deltay    := ccout2 - cpout2
      ;Ein Delta sollte Null sein - da
      If(deltax = 0){
         ;y verschiebung, hoch runter
         If(deltay = -1){       ;Up
            THEPATH2 := "{UP}" THEPATH2
         }else if(deltay = 1){  ;down
            THEPATH2 := "{DOWN}" THEPATH2
         }else{
            msgbox,16,ERROR, % "deltay has unexpectet value! (should be 1 or -1) but has: " deltay
         }
      }else if(deltay = 0){
         ;x verschiebung, links rechts
         If(deltax = -1){       ;rechts
            THEPATH2 := "{LEFT}" THEPATH2
         }else if(deltax = 1){  ;links
            THEPATH2 := "{RIGHT}" THEPATH2
         }else{
            msgbox,16,ERROR, % "deltax has unexpectet value! (should be 1 or -1) but has: " deltax
         }
      }else{
         msgbox,16, Error, % "Der Pfad kann nicht zurückgerechnet werden!`ndelta x: " deltax " und delta y: " deltay
      }
      
      
      THEPATH := "{" parent_FNr "} ---> " THEPATH   
      If(parent_FNr = START_FIELD){
         break
      }
      FieldNr := parent_FNr
   }
   return, THEPATH2
} ;**************************************************************

/****************************************************************
Gibt das Vorgängerfeld (parent) des übergebenen Feldes zurück.
*****************************************************************
*/
get_parent(FNr){
global
[color=darkred];    return, AS_parent_%FNr%[/color]
   ; Lexikos: Get value from UINT array at index FNr.
   [color=indigo]return NumGet(AS_parent, (FNr-1)*4)[/color]
} ;**************************************************************

/****************************************************************
Entfernt alle Zeichen, die keine Nummern sind.
*****************************************************************
*/
trim_num(str){
 Loop, parse,str
 {
 If a_loopfield is Number
   new .= a_loopfield
   }
return, new 
} ;**************************************************************


/****************************************************************
Lädt ein Levelzustand, und macht eine Pre-analysis. Dabei
werden nicht benutzbare Felder bereits in die Closedlist ein-
getragen.
*****************************************************************
*/

LOAD_leveL(leveldmp){
global
static cnt
      cnt := 1
      ;clean up
[color=darkred];       A_DEL(AS_FIELD_COORD)[/color]
[color=darkred];       A_DEL(AS_fVALUE_Field)[/color]
[color=darkred];       A_DEL(AS_COST_Field)[/color]
      A_DEL(AS_OPENLIST)
[color=darkred];       A_DEL(AS_ClosedList)[/color]
      
      ; Lexikos: First, get size of map.
      [color=indigo]GameH =
      GameW =
      Loop,Parse,leveldmp,`n
      {
         if A_LoopField = ; Lexikos: Empty line. Should be end of file.
            break
         GameH := A_Index
         if GameW =
            GameW := StrLen(A_LoopField)
         else if (GameW != StrLen(A_LoopField))
            return "" ; Lexikos: Map error (non-rectangular).
      }
      if (GameH="" || GameW="")
          return "" ; Lexikos: Map error.[/color]
      
      ; Lexikos: Initialize array of UINT to hold parent of each node.
      [color=indigo]VarSetCapacity(AS_parent, GameW*GameH*4, 0)[/color]
      
      ;*Lexikos: Initialize array of bytes to keep track of which nodes have been opened/closed.
      [color=indigo]VarSetCapacity(AS_opened, GameW*GameH, 0)[/color]
      
      ; Lexikos: Store exact level text in global var instead of dynamic vars (see GetField()).
      [color=indigo]Gleveldmp := leveldmp[/color]
      
[color=darkred];       loop,Parse,leveldmp,`n[/color]
[color=darkred];       {[/color]
[color=darkred];          y := A_Index[/color]
[color=darkred];          Loop,Parse,A_LoopField[/color]
[color=darkred];          {[/color]
[color=darkred];             x := A_Index[/color]
[color=darkred];             GX%x%Y%y%   := A_LoopField                      ;speichert  das LEvel in[/color] einen Array
[color=darkred];             GNrX%x%Y%y% := cnt                              ;speichert zu jeder coord die[/color] Feldnummer
[color=darkred];             z := x "|" y[/color]
[color=darkred];             A_Put(AS_FIELD_COORD,z,cnt)                     ;speichert die Koordinaten[/color] für jedes Feld.
[color=darkred];             ; Lexikos: Above not necessary due to changes elsewhere.[/color]
[color=darkred];             ;hier wird voranalysert:[/color]
[color=darkred];             If (A_LoopField = "1"){[/color]
[color=darkred];                p1 := x " " y                    ;player coordinates[/color]
[color=darkred];                p1x := x, p1y := y[/color]
[color=darkred];                A_Put(AS_OPENLIST, cnt)[/color]
[color=darkred];             }else If (A_LoopField = "X"){       ;undestructable wall[/color]
[color=darkred];                A_Put(AS_ClosedList, cnt)[/color]
[color=darkred];             }else If (A_LoopField = "T"){       ;Target[/color]
[color=darkred];                t1x := x, t1y := y[/color]
[color=darkred];             }[/color]
[color=darkred];             ++cnt[/color]
[color=darkred];          }[/color]
[color=darkred];       }[/color]

      ; Lexikos: Instead of the above loop, we can find the "1" and "T" directly via InStr.
      ;          Other parts of the loop are made obsolete by changes elsewhere in the script.

      [color=indigo]p1 := InStr(Gleveldmp, "1")
      p1x := Mod(p1-1,GameW+1)+1
      p1y := (p1-1)//(GameW+1)+1
      p1 := p1x " " p1y
      A_Put(AS_OPENLIST, cnt:=GetFieldNr(p1x,p1y))
      ;*Lexikos: Set "opened" status of this field.
      [color=indigo]NumPut(1, AS_opened, cnt-1, "char")[/color]
      
      t1 := InStr(Gleveldmp, "T")
      t1x := Mod(t1-1,GameW+1)+1
      t1y := (t1-1)//(GameW+1)+1
      t1 := t1x " " t1y[/color]

} ;****************************************************************

/******************************************************************
Einfacherer Array zugriff.
*******************************************************************
*/
GETField(x,y){
   global
[color=darkred];    return, % GX%x%Y%y%      [/color]
   ; Lexikos: Grab the field value directly from the level text.
   [color=indigo]return SubStr(Gleveldmp, (y-1)*(GameW+1)+x, 1)[/color]
}
GetFieldNr(x,y){
   global
[color=darkred];    return, % GNrX%x%Y%y%[/color]
   ; Lexikos: Derive the FieldNr from the coords.
   [color=indigo]return (y-1)*GameW+x[/color]
}
;*****************************************************************

/******************************************************
Durchsucht einen Array und gibt true zurück,
wenn val gefunden wird.
*******************************************************
*/
IsValinArray(byref Array,val){
global  
   Loop, % A_Count(Array)   
   {
      If(A_Get(Array, a_Index) = val){
         return, true
      }
   }
   return, false
} ;*****************************************************

/*******************************************************
Durchsucht einen Array nach der val und löscht das item,
welches val enthällt. Beim erstentreffer wird die suche
abgebrochen.
********************************************************
*/
DeleteValInArray(byref Array,val){
global   
   Loop, % A_Count(Array)   
   {
      
      If(A_Get(Array, a_Index) = val){
         A_Del(Array, a_Index)
         return, true
      }
   }
   return, false
} ;******************************************************
Because the field number can be calculated form the coords and vice versa, AS_FIELD_COORD and GNrXxYy aren't necessary. With similar calculation, the field can be retrieved directly from leveldmp, removing the need for GXxYy.

I converted AS_parent_%FNr%, AS_fVALUE_Field and AS_COST_Field into more efficient UINT arrays using VarSetCapacity, NumPut and NumGet. I also made some misc optimizations, such as removing an unnecessary loop in GetNextField.

At this point, the time needed for HARD01.map had shrunk from ~8.8 seconds to ~7.0 seconds.

I then found this optimization: don't add "X" fields to AS_ClosedList. Since "X" always means "closed", there is no need. The fewer items in the list, the less time it takes to search through the list. Additionally, it avoids searching the list at all for "X" fields. HARD01.map now takes ~2.1 seconds on my system, down from ~8.8. :shock:

Obviously, the last optimization doesn't help with large empty areas, where there is no "X" to begin with.

I'm sure there are more optimizations to make, but I've done enough for today. :)

Edit: Maybe not. :lol: I've added another optimization: mark each field as "opened" once it enters the open list. (I've done this by using an array of bytes containing 0 or 1, with one byte per field.) This allows us to quickly check if a field has been opened (whether it is currently open or closed) without searching through a list. It also entirely removes the need for AS_ClosedList. This cut the time for HARD01.map on my system down to ~0.28 seconds! An empty 40x40 map is now ~8.9 seconds instead of ~120!! :shock: :shock:
--End Edit


I also found it interesting that running the script on the latest beta cut the time almost in half.

#8 Translater

Translater
  • Guests

Posted 13 January 2009 - 04:48 PM

I´m DHMH :)
yes, i´ve translated it!
:)
Good script! Maybe you can improve the performance...
the red color blinks sometimes... (you can try to use gdi+ :) )
Greets,
DHMH

#9 IsNull

IsNull
  • Fellows
  • 990 posts

Posted 15 January 2009 - 07:08 PM

dear Lexikos,

I'm glad to see your effort to optimize the performance. I will study your improvements and update the code in a new version. Thanks alot. :)

I also found it interesting that running the script on the latest beta cut the time almost in half.

Yes, I use for myself only the Beta-intrerpreter. I've replaced the stable with this one. :wink:

@DHMH, As you maby noticed, derRaphael is working on a Bombman-Game, and I try to create a AI Bot. To make it short: I will use dR's game-engine, which bases on gdi+ to display the pathfinding. At the moment, I'm waiting for a Interface to connect to the engine.

This pathfinding-algo is grown up only therefore. I need it for the AI :) It's now much faster.


EDIT: Initial posting updatet with improved Algo. :)

#10 Laszlo

Laszlo
  • Fellows
  • 4713 posts

Posted 15 January 2009 - 07:55 PM

Cool! It is 50 times faster now on 40x40 maps! If only the graphics could be similarly accelerated...

#11 SoggyDog

SoggyDog
  • Members
  • 803 posts

Posted 15 January 2009 - 08:39 PM

Did I do something wrong?
Unzipped package, ran the script, loaded a map and clicked Walk.

Posted Image

#12 IsNull

IsNull
  • Fellows
  • 990 posts

Posted 16 January 2009 - 01:07 PM

Hey, SoggyDog
replace pathfinder.ahk with this one:

/**********************************************************************
PFADFINDER + LEVELEDITOR - Pre ALPHA
ver 0.1
coded by IsNull - 01.01.2009

TODO:
-----------
- easy save current map

***********************************************************************
*/
#NoEnv  ; Recommended for performance and compatibility with future AutoHotkey releases.
SendMode Input  ; Recommended for new scripts due to its superior speed and reliability.
#SingleInstance, force
SetWorkingDir %A_ScriptDir%  ; Ensures a consistent starting directory.
SetBatchLines, -1
;---------------------------------------------------------------------------------------
#Include, %A_ScriptDir%\INCLUDE\AStar.ahk
#Include, %A_ScriptDir%\INCLUDE\pfadfinder.dialoge.ahk
;----------------
;-------------------
G_BEGEHBAR	:= " "
G_WALL_UD	:= "X"
G_TARGET	:= "T"
G_PLAYER	:= "1"
;-------------------------------------------
ver 		:= "0.3 ALPHA"
SkinPath	:= A_Temp
;-------------------------------------------
;Copy immages into temp:

Loop,%A_ScriptDir%\gfx\*.*
{
	SplitPath,A_LoopFileFullPath,Filename
	FileCopy, %A_LoopFileFullPath%, %SkinPath%\%Filename%, 0
}
;-------------------------------------------
Loop, %0%
	p%a_index% := %A_index%
	
If(p1 != ""){
	IfNotExist, %p2%
	{
		MsgBox,16,ERROR, Die Map konnte nicht gefunden werden!`n%p2%(file missing)
		p1 := ""
	}else{
		filename := p2
	}
}
If(p1 != "astar"){
	OnMessage(0x200, "WM_MOUSEMOVE")

	Gui, 1:default
	Gui, Color, white
	GUI, add, EDIT, vwith w50 yP+30 x10 h20,10
	GUI, add, EDIT, vhight w50 yp xP+70 h20,10
	GUI, add, Button, gCreateMAP xp+60 yp, [.create]

	GUI, add, text, x10 yp+50  w100,Brush:
	GUI, add, DDl, x10 yp+20  w120 vDDL_BRUSH gCHANGE_BRUSH,Begehbar|WALL UD||PLAYER|TARGET
	GUi, font, s10,courier
	GUI, add, EDIT, x10 yp+50 w300 h300 vMAP_DUMP
	GUi, font,
	Menu, FileMenu, Add, &Open Map    Ctrl+O, MenuFileOpen  ; See remarks below about Ctrl+O.
	Menu, FileMenu, Add, &Export Map    Ctrl+E, MenuFileExport
	Menu, FileMenu, Add, &SHOW Map    Ctrl+S, MenuFileSHOW
	Menu, MenuA_STAR, Add, WALK, MenuA_STAR
	Menu, FileMenu, Add, E&xit, MenuHandler
	Menu, HelpMenu, Add, &About, MenuAbout
	Menu, MyMenuBar, Add, &MAP, :FileMenu  ; Attach the two sub-menus that were created above.
	Menu, MyMenuBar, Add, &A-Star, :MenuA_STAR
	Menu, MyMenuBar, Add, &Help, :HelpMenu
	Gui, Menu, MyMenuBar


	Gui, show, h420 w320 ,Labyrint Leveleditor %ver%
	GUI, +LastFound
	Dock_HostID := WinExist()
	Gosub, CHANGE_BRUSH
}else{
	FileRead, map, %p2%
	IMPORT_MAP(map)
	CreateGUI(G_DIMENSION_W,G_DIMENSION_H,1)
	Gosub, RUN_ASTAR
}

IF(p1 = "load"){
	FileRead, map, %p2%
	IMPORT_MAP(map)
	CreateGUI(G_DIMENSION_W,G_DIMENSION_H,1)
	}
return
;####################################################################
MenuHandler:
	ExitApp
return
/*
#IfWinActive, Level Map
Up::
Down::
Left::
Right::
	If(p1 = "astar"){
		Return
	}
	MOVE_PLAYER(A_ThisLabel)
return
*/


MenuA_STAR:
	cmd = "%A_ScriptDir%\%A_ScriptName%" astar "%filename%"
	FileDelete, %A_Temp%\run.bat
	FileAppend, % cmd, %A_Temp%\run.bat
	run, %A_Temp%\run.bat,,Hide
return

RUN_ASTAR:
	LOAD_leveL(EXPORT_MAP())
	FieldCNT := GameH * GameW
	SplashImage, %A_ScriptDir%\gfx\astar_spalsh.jpg, , calculating path,, A* Calculation
	myway := astar()
	SplashImage , OFF
	If(!myway){
		msgbox,64,Warnung, Leider existiert keine Möglichkeit, das Ziel zu erreichen.
		return
	}
	WALK_WAY(myway)
	cmd = "%A_ScriptDir%\%A_ScriptName%" load "%filename%"
	FileDelete, %A_Temp%\run.bat
	FileAppend, % cmd, %A_Temp%\run.bat
	run, %A_Temp%\run.bat,,Hide
return



WALK_WAY(WAY){
global
cycle	:= 300 ;ms	
	Loop, parse, WAY, },{
	{
		If(A_LoopField = ""){
			Continue
		}
		MOVE_PLAYER(A_LoopField)
		sleep, % cycle
	}
}



MenuAbout:
	msg 	:= "Create easy Labyrint-Levelmaps and let the Tool find a path from Player to Target. Core of this Project is the A*-Algorythm.`n`nThe " 
			.  "pathfinding A* (A-Star) Algorythm search the optimal path. Then, the Script will show it with animations.`n`nCoded by IsNull 2009"
			.  "`n::Librarys::`n`n"
			.  "`tDock `t`tby majkinetor`t`tver 1.0`n"
			.  "`tBin Array `tby derRaphael`t`tver RC2`n"
			.  "`tastar `t`tby IsNull + Lexikos`tver " astar_ver 
			
			HNDL 	:= DIALOGE_SPAN(msg)
	sleep, 7000
	DIALOGE_SPAN_KILL(HNDL)
return
;-------------------------------------------

MenuFileSHOW:
	GUI, 1:Default
	GuiControl,,MAP_DUMP, % EXPORT_MAP()
	GUI, 2:Default
return

MenuFileExport:
	map_dump	:= EXPORT_MAP()
	FileSelectFile,filename, S,%a_scriptdir%\MAPS,Speichern sie die Map,*.map
	If("map" != substr(filename,strlen(filename)-2)){
		filename .= ".map"
	}
	FileDelete, % filename
	FileAppend, % map_dump, % filename
	run, notepad.exe %filename%
return


MenuFileOpen:
	FileSelectFile,filename, ,%a_scriptdir%\MAPS,Wählen sie die zu öffnende Map,*.map
	FileRead, map_dump, % filename
	IMPORT_MAP(map_dump)
	CreateGUI(G_DIMENSION_W,G_DIMENSION_H,1)
return



/************************************************
Parst den MAP-Array und schreibt eine ASCII-MAP
*************************************************
*/
EXPORT_MAP(){
global
	x := 1, y := 1
	map_dump	:= ""
	Loop, % G_DIMENSION_H
	{
		Loop, % G_DIMENSION_W
		{
			map_dump .= GMAP_X%x%Y%y%
			x += 1
		}
		x := 1
		y += 1
		map_dump .= "`n"
	}
	return, map_dump
} ;**********************************************

/***************************************************
Importiert eine ASCII-MAP und schreibt sie in den 
MAP-ARRAY
****************************************************
*/
IMPORT_MAP(map_dump){
global
	xCRD	:= 1
	yCRD	:= 1
	G_DIMENSION_W	:= 0
	G_DIMENSION_H	:= 0
	
	Loop, parse, map_dump, `n, `r
	{
		If(A_LoopField = ""){
			Continue
		}
		Loop, parse, A_LoopField
		{
			GMAP_X%xCRD%Y%yCRD% := A_LoopField
			xCRD	+= 1
		}
		yCRD	+= 1
		UPDATEMAX(G_DIMENSION_H,yCRD)
		UPDATEMAX(G_DIMENSION_W,xCRD)
		xCRD	:= 1
	}
	G_DIMENSION_W -= 1
	G_DIMENSION_H -= 1
	return, 1
} ;************************************************


UPDATEMAX(byref var,val){
	IF(var = ""){
		var := val
	}else If (var  < val){
		var := val
	}
}

CHANGE_BRUSH:
	GUi, submit, nohide
	If(DDL_BRUSH = "WALL UD"){
		G_PIC	:= SkinPath "\wall.bmp"
		G_SIGN	:= G_WALL_UD
	}else if (DDL_BRUSH = "Begehbar"){
		G_PIC	:= SkinPath "\begehbar.bmp"
		G_SIGN	:= G_BEGEHBAR
	}else if (DDL_BRUSH = "PLAYER"){
		G_PIC	:= SkinPath "\player.bmp"
		G_SIGN	:= G_PLAYER
	}else if (DDL_BRUSH = "TARGET"){
		G_PIC	:= SkinPath "\TARGET.bmp"
		G_SIGN	:= G_TARGET
	}
return

CreateMAP:
	Gui, submit, NoHide
	CreateGUI(with,hight)
return


GuiClose:
	Exitapp
return


/*********************************************************************
Erstellt ein neues GUI
**********************************************************************
*/
CreateGUI(w,h,load = 0){
global
;----------------
Fwith	:= Fhight := 20
XPOS	:= 10
YPOS	:= 10

xCRD	:= 1
yCRD	:= 1
EDITOR_NAME := "Level Map (" w " x " h ")"
G_DIMENSION_W := w
G_DIMENSION_H := h
;----------------
Gui, 2:Default
Gui, destroy
Gui, Color, black
	FeldNr := 1
	Loop, % G_DIMENSION_H
	{
		Loop, % G_DIMENSION_W
		{
				;erstelle neues, leeres Spielfeld
				Gui, add, Picture, w%Fwith% h%Fhight% vFELD%FeldNr% hwndFELDID%FeldNr% x%XPOS% y%YPOS%, %SkinPath%\begehbar.bmp
				If(!load){
					GMAP_X%xCRD%Y%yCRD%	:= G_BEGEHBAR
				}else{
					Type_ 	:=	GMAP_X%xCRD%Y%yCRD%
					If(Type_ = "X"){
						GuiControl,,FELD%FeldNr%, %SkinPath%\wall.bmp
					}else if (Type_ = " "){
						GuiControl,,FELD%FeldNr%, %SkinPath%\begehbar.bmp
					}else if (Type_ = "T"){
						GuiControl,,FELD%FeldNr%, %SkinPath%\TARGET.bmp
						CURRENT_TARGET_X := xCRD
						CURRENT_TARGET_Y := yCRD
					}else if (Type_ = "1"){
						GuiControl,,FELD%FeldNr%, %SkinPath%\player.bmp
						CURRENT_PLAYER_X := xCRD
						CURRENT_PLAYER_Y := yCRD
					}
				}
				GFNr_X%xCRD%Y%yCRD%	:= FeldNr
				%FeldNr%_COORD	:= xCRD "|" yCRD
				XPOS += 21
				++xCRD 
				++FeldNr
		}
		YPOS 	+= 21
		XPOS	:= 10
		yCRD	+= 1
		xCRD	:= 1
	}
	Gui, add, StatusBar,,
	SB_SetParts(100)
	SB_SetText("Map loaded", 2)
	Gui, show, , % EDITOR_NAME
	Gui,+Lastfound
	GUI_ID := WinExist()
	
	Dock(GUI_ID, "1,0,10, 0,0,0")
} ;******************************************************************

/********************************************************************

section_
0	= UPDATE FULL MAP
1	= UPDATE PLAYER RANGE
2	= UPDATE TARGET RANGE
*********************************************************************
*/
UPDATE_GUI(section_ = 0){
global	
	xCRD	:= 1
	yCRD	:= 1
	FeldNr 	:= 1
	Gui, 2:Default
	Loop, % G_DIMENSION_H
	{
		Loop, % G_DIMENSION_W
		{
			Ignore_ := false
			IF(section_ = 1){
				If(like_one(CURRENT_PLAYER_Y,yCRD) AND like_one(CURRENT_PLAYER_X,xCRD)){
					;sind ähnlich
				}else{
					Ignore_ := true
				}
			}else IF(section_ = 2){
				If(like_one(CURRENT_TARGET_Y,yCRD) AND like_one(CURRENT_TARGET_X,xCRD)){
					;sind ähnlich
				}else{
					Ignore_ := true
				}
			}
			If(!Ignore_){
				Type_ 	:=	GMAP_X%xCRD%Y%yCRD%
				If(Type_ = "X"){
					GuiControl,,FELD%FeldNr%, %SkinPath%\wall.bmp
				}else if (Type_ = " "){
					GuiControl,,FELD%FeldNr%, %SkinPath%\begehbar.bmp
				}else if (Type_ = "T"){
					GuiControl,,FELD%FeldNr%, %SkinPath%\TARGET.bmp
					CURRENT_TARGET_X := xCRD
					CURRENT_TARGET_Y := yCRD
				}else if (Type_ = "1"){
					GuiControl,,FELD%FeldNr%, %SkinPath%\player.bmp
					CURRENT_PLAYER_X := xCRD
					CURRENT_PLAYER_Y := yCRD
				}else{
					GuiControl,,FELD%FeldNr%, %SkinPath%\begehbar.bmp
				}
			}
			GFNr_X%xCRD%Y%yCRD%	:= FeldNr
			%FeldNr%_COORD	:= xCRD "|" yCRD
			++xCRD 
			++FeldNr
		}
		yCRD	+= 1
		xCRD	:= 1
	}
}

/********************************
*********************************
*/
like_one(z1,z2){
	IF(z1 = z2){
		return, 1
	}else if (z1 = (z2 + 1)){
		return, 1
	}else if (z1 = (z2 - 1)){
		return, 1
	}else{
		return, 0
	}
} ;******************************


GETFieldNr02(x,y){
global
	return, GFNr_X%x%Y%y%
}
GetFieldCoord(FNr){
global
	Return, %FNr%_COORD
}

SETField(typ,FNr,G_PIC){
global
	If(FNr = ""){
		return, 0
	}
	GuiControl,,FELD%NR%, %G_PIC%
	cc := GetFieldCoord(FNr)
	pos := RegExMatch(cc,"([0-9]*)\|([0-9]*)",out)
	If(!pos){
		return, 0
	}
	GMAP_X%out1%Y%out2% := typ
	return, 1
}


MOVE_PLAYER(DIRECTION){
global
	If((CURRENT_PLAYER_X = "") OR (CURRENT_PLAYER_Y = "")){
		return
	}
	STOP_SCAN := true
	new_posx := CURRENT_PLAYER_X
	new_posy := CURRENT_PLAYER_Y
	
	If(DIRECTION = "UP"){
		new_posy	-= 1
	}else if (DIRECTION = "DOWN"){
		new_posy	+= 1
	}else if (DIRECTION = "LEFT"){
		new_posx	-= 1
	}else if (DIRECTION = "RIGHT"){
		new_posx	+= 1
	}else{
		msgbox,16,ERROR, % "UNKNOWN Direction: " DIRECTION
	}
	
	
	If((new_posx < 1) OR (new_posy < 1)){
		return
	}
	If((new_posx > G_DIMENSION_W) OR (new_posy > G_DIMENSION_H)){
		return
	}
	
	ZielFeld := GMAP_X%new_posx%Y%new_posy%
	If(ZielFeld = "X"){
		SoundBeep, 500,500
		return
	}
	
	NEW_PLAYER_FIELD	:= GETFieldNr02(new_posx,new_posy)
	SET_PLAYER(NEW_PLAYER_FIELD)
	STOP_SCAN := false
	If (ZielFeld = "T"){
		MsgBox,64,Gratualtion, Ziel erreicht :) 
	}
}


SET_PLAYER(FNr){
global
	;Akutelle Playercoord ermitteln:
	cc := GetFieldCoord(FNr)
	RegExMatch(cc,"([0-9]*)\|([0-9]*)",a)
	If(a1 = CURRENT_PLAYER_X) AND (a2 = CURRENT_PLAYER_Y){
		Return
	}

	;löschen des alten Players
	OLDPL_NR := GETFieldNr02(CURRENT_PLAYER_X,CURRENT_PLAYER_Y)
	SETField(G_BEGEHBAR,OLDPL_NR,SkinPath "\begehbar.bmp")
	UPDATE_GUI(1)
	CURRENT_PLAYER_X := a1
	CURRENT_PLAYER_Y := a2
	PNr_current	:=	GETFieldNr02(CURRENT_PLAYER_X,CURRENT_PLAYER_Y)
	SETField(G_PLAYER,PNr_current,SkinPath "\player.bmp")
	UPDATE_GUI(1)
}

SET_TARGET(FNr){
global
	
	;Akutelle Playercoord ermitteln:
	cc := GetFieldCoord(FNr)
	RegExMatch(cc,"([0-9]*)\|([0-9]*)",a)
	If(a1 = CURRENT_TARGET_X) AND (a2 = CURRENT_TARGET_Y){
		Return
	}
	
	;löschen des alten Players
	OLDPL_NR := GETFieldNr02(CURRENT_TARGET_X,CURRENT_TARGET_Y)
	SETField(G_BEGEHBAR,OLDPL_NR,SkinPath "\begehbar.bmp")
	UPDATE_GUI(2)
	CURRENT_TARGET_X := a1
	CURRENT_TARGET_Y := a2
	TNr_current	:=	GETFieldNr02(CURRENT_TARGET_X,CURRENT_TARGET_Y)
	SETField(G_TARGET,TNr_current,SkinPath "\TARGET.bmp")
	UPDATE_GUI(2)
}

/**************************************
									*
***************************************
*/
WM_MOUSEMOVE(){
global
	If(STOP_SCAN){
		return
	}
	MouseGetPos,, , OutputVarWin, OutputVarControl
	If(OutputVarWin != GUI_ID){
		return, 1
	}
	NR := substr(OutputVarControl,strlen("static") + 1)
	SB_SetText("Field: " NR, 1)
	
	If(GetKeyState("LButton")){
		Gui,submit, nohide
		if (DDL_BRUSH = "PLAYER"){
			SET_PLAYER(NR)
		}else if (DDL_BRUSH = "TARGET"){
			SET_TARGET(NR)
		}else{
			SETField(G_SIGN,NR,G_PIC)
		}
		Gosub, MenuFileSHOW
	}
	If(GetKeyState("RButton")){
		SETField(G_BEGEHBAR,NR,SkinPath "\begehbar.bmp")
	}
	return, 1
}
#Include, %A_ScriptDir%\INCLUDE\dock.ahk

Hope it works :)

#13 SoggyDog

SoggyDog
  • Members
  • 803 posts

Posted 16 January 2009 - 02:18 PM

Indeed, it does.

Thank you, IsNull.

#14 IsNull

IsNull
  • Fellows
  • 990 posts

Posted 17 January 2009 - 10:10 AM

Indeed, it does.

Thank you, IsNull.

I've updated initial posting. :) Some bug and comfort-fixings.