I needed a specific type of pathfinding for a project and I usually code things in ahk first before converting to c++, so performance may not be amazing but it's great for just learning how algorithms work and I thought it would be fun to share =P
The majorty of the code is drawing related, the important bit is done at the algorithm: label
CONTROLS: Left Click - Set Solid, Right Click - Remove Solid, Middle Click - Set Goal
Code: Select all
#NoEnv
#SingleInstance, Force
SendMode, Input
SetBatchLines, -1
SetWorkingDir, %A_ScriptDir%
ifnotexist,ShinsGameClass.ahk
{
msgbox,4,Missing lib, You are missing ShinsGameClass.ahk`, Would you like to automatically download it from github?`n`nPress Yes to download`, No to exitapp
ifmsgbox,yes
{
urldownloadtofile,% "https://raw.githubusercontent.com/Spawnova/ShinsGameClass/main/AHK%20V1/ShinsGameClass.ahk", ShinsGameClass.ahk
reload
} else {
exitapp
}
}
#include *i ShinsGameClass.ahk
DIRECTIONS := [{x:0,y:-1},{x:-1,y:0},{x:1,y:0},{x:0,y:1}] ;possible directions
DIRECTIONS8 := [{x:-1,y:-1},{x:0,y:-1},{x:1,y:-1},{x:-1,y:0},{x:1,y:0},{x:-1,y:1},{x:0,y:1},{x:1,y:1}] ;for finding optimal paths later
TILES_ROW := 32
TILES_COL := 32
TILES_SIZE := 28
TILES_SIZE_HALF := round(TILES_SIZE/2)
Width := TILES_ROW * TILES_SIZE
Height := TILES_COL * TILES_SIZE
GridY := 40
Game := new ShinsGameClass(0,0,Width,Height + GridY,"Dijkstra Map - Example by Spawnova",1)
;initialize the map, [solid,x,y,cost,effectVar,xdir,yDir] ;effect is for drawing, not needed
Grid := []
loop % TILES_ROW {
x := a_index-1
loop % TILES_COL {
y := a_index-1
Grid[x,y] := {s:0,x:x,y:y,cost:0xFFFF,a:0,xDir:0,yDir:0}
}
}
goalX := round(TILES_ROW / 2)
goalY := round(TILES_COL / 2)
options := []
options["numbers"] := new _button(game.width-115,6,110,30,"Numbers","Draw numbers",0)
options["arrows"] := new _button(game.width-220,6,95,30,"Arrows","Draw arrows",0)
options["mouse"] := new _button(game.width-360,6,130,30,"Mouse Path","Shows the path at the current mouse position",0)
Updating := true ;handles when to update the map
loop {
if (Game.BeginDraw()) {
game.fillrectangle(0,0,game.width,GridY,0xFF003300,3)
game.DrawRectangle(2,2,game.width-3,GridY-3,0xFF000000,2)
game.drawtext(game.fps,0,0,16,0xFFFFFFFF)
hoverX := hoverY := -1
inc := 280 / (maxDist) ;for color purposes
loop % TILES_ROW {
x := a_index-1
loop % TILES_COL {
y := a_index-1
s := TILES_SIZE - Grid[x,y].a ;adds small effect when clicking
tx := x*s
ty := GridY + y*s
hover := (game.mouseX >= tx and game.mouseX < tx+s and game.mouseY >= ty and game.mouseY < ty+s)
if (hover) {
hoverX := x
hoverY := y
if (!updating) {
if (game.lbutton and !Grid[x,y].s) {
Grid[x,y].s := 1
Grid[x,y].a := 0.33
updating := 1
} else if (game.rbutton and Grid[x,y].s) {
Grid[x,y].s := 0
Grid[x,y].a := 0.33
updating := 1
} else if (game.mbuttonD and grid[x,y]) {
GoalX := x
GoalY := y
updating := 1
}
}
}
if (Grid[x,y].a > 0) {
Grid[x,y].a := max(0,Grid[x,y].a - (1 * game.timescale))
}
game.FillRectangle(tx+1,ty+1,s-2,s-2,(Grid[x,y].cost = 0 ? 0xFFFFFFFF : Grid[x,y].s ? 0xFF111111 : Grid[x,y].cost = 0xFFFF ? 0xFF444444 : HsvToRGB(abs(Grid[x,y].cost*inc),100,80)))
if (Grid[x,y].s = 0 and Grid[x,y].cost != 0xFFFF and options["arrows"].state) {
x1 := tx + TILES_SIZE_HALF + (Grid[x,y].xDir * TILES_SIZE_HALF)
y1 := ty + TILES_SIZE_HALF + (Grid[x,y].yDir * TILES_SIZE_HALF)
game.drawline(tx+TILES_SIZE_HALF,ty+TILES_SIZE_HALF,x1,y1,0xFFFFFFFF)
}
if (Grid[x,y].cost != 0xFFFF and options["numbers"].state)
game.drawtext(Grid[x,y].cost,tx+TILES_SIZE_HALF-50,ty+4,TILES_SIZE_HALF,(Grid[x,y].cost = 0 ? 0xFF000000 : 0xFFFFFFFF),"Arial","acenter w100 bold")
}
}
if (hoverX >= 0)
game.DrawRectangle((hoverX*TILES_SIZE)+1,GridY+(hoverY*TILES_SIZE)+1,TILES_SIZE-2,TILES_SIZE-2,0xFFFFFFFF,1) ;draw hover
for k,v in options
v.draw(game)
if (options["mouse"].state and game.MouseInClient) { ;drawing the mouse path
tx := floor(game.mousex / TILES_SIZE) ;convert mouse position to tile position
ty := floor((game.mousey-gridY) / TILES_SIZE)
if (tx >= 0 and ty >= 0 and tx < TILES_ROW and ty < TILES_COL) { ;if within tile map
path := GetPathToGoal(tx,ty,grid)
sx := (tx * TILES_SIZE) + TILES_SIZE_HALF ;convert back to client space
sy := GridY + (ty * TILES_SIZE) + TILES_SIZE_HALF
for k,v in path {
cx := (v.x * TILES_SIZE) + TILES_SIZE_HALF
cy := GridY + (v.y * TILES_SIZE) + TILES_SIZE_HALF
game.DrawLine(sx,sy,cx,cy,0xFF000000,5)
game.DrawLine(sx,sy,cx,cy,0xFFFFFFFF,3)
sx := cx
sy := cy
}
}
}
Game.EndDraw()
} else {
sleep 10
}
if (updating) {
gosub algorithm
updating := 0
}
}
return
;There is where the algorithm actually determines the map
algorithm:
MaxDist := 0 ;for color
;reset map costs
loop % TILES_ROW {
x := a_index-1
loop % TILES_COL {
y := a_index-1
Grid[x,y].cost := 0xFFFF ;set to large number, i use this to determine if it's valid later
}
}
;start with the goal node setting it's cost to 0, then progress outwards
Grid[goalX,goalY].cost := 0
queue := [Grid[goalX,goalY]]
while (queue.length() > 0) {
node := queue.removeat(1) ;remove the earliest node
for k,v in DIRECTIONS { ;loop through the neighbors
tx := node.x + v.x
ty := node.y + v.y
if (tx >= 0 and tx < TILES_ROW and ty >= 0 and ty < TILES_COL and !Grid[tx,ty].s and Grid[tx,ty].cost = 0xFFFF) { ;if within the tile map and not solid and no cost set yet
lc := node.cost ;lowest cost default
for kk,vv in DIRECTIONS { ;loop through node neighbors and get the lowest cost neighbor
tx2 := tx + vv.x
ty2 := ty + vv.y
if (tx2 >= 0 and tx2 < TILES_ROW and ty2 >= 0 and ty2 < TILES_COL and !Grid[tx2,ty2].s and Grid[tx2,ty2].cost < lc) { ;if a neighbor has a lower cost use that
lc := Grid[tx2,ty2].cost
}
}
if (lc > maxDist) ;for color purposes, not needed for algorithm
maxDist := lc
Grid[tx,ty].cost := lc + 1 ;set this nodes cost to the lowest neighbor + 1
queue.push(Grid[tx,ty]) ;add this node to the queue to have its neghbors checked later
}
}
}
;set directions, technically could be set above, but I want to specify diagonal movement
loop % TILES_ROW {
x := a_index-1
loop % TILES_COL {
y := a_index-1
lc := 0xFFFF
for k,v in DIRECTIONS8 {
tx := x + v.x
ty := y + v.y
if (tx >= 0 and tx < TILES_ROW and ty >= 0 and ty < TILES_COL and Grid[tx,ty].cost < lc) {
if (Abs(Grid[x,y].cost - Grid[tx,ty].cost) <= 2) { ;ignore holes in walls, kinda clunky
lc := Grid[tx,ty].cost
Grid[x,y].xDir := v.x
Grid[x,y].yDir := v.y
}
}
}
}
}
return
;traverse the map and add the directions to the path until goal is reached
GetPathToGoal(x,y,grid) {
path := []
if (grid[x,y].cost != 0xFFFF) { ;if the starting spot is invalid return
loop {
xDir := grid[x,y].xDir
yDir := grid[x,y].yDir
x += xDir
y += yDir
path.push({x:x,y:y})
if (grid[x,y].cost = 0)
break
if (grid[x,y].cost = 0xFFFF) ;should never happen
break
}
}
return path
}
;simple button class
class _Button {
__New(x,y,w,h,text,tooltip,state:=-1) {
this.x := x
this.y := y
this.w := w
this.h := h
this.text := text
this.tooltip := tooltip
this.state := state
}
Draw(game) {
hover := (game.mouseX >= this.x and game.mouseY >= this.y and game.mouseX < this.x+this.w and game.mouseY < this.y+this.h)
game.fillrectangle(this.x,this.y,this.w,this.h,(hover ? 0xFF666666 : 0xFF111111))
game.Drawrectangle(this.x,this.y,this.w,this.h,0xFF000000)
dx := 0
if (this.state != -1) {
if (hover and game.lbuttond) {
this.state := !this.state
}
dx := this.h/2
game.fillellipse(this.x+dx,this.y+dx,dx-6,dx-6,(this.state ? 0xFF00FF00 : 0xFFFF0000))
game.drawellipse(this.x+dx,this.y+dx,dx-6,dx-6,0xFF000000)
}
game.drawtext(this.text,this.x + dx*2,this.y+2,18,0xFFAAAAAA,"Arial")
if (hover) {
metrics := game.GetTextMetrics(this.tooltip,20,"Arial")
dx := this.x
dy := this.y + this.h + 2
w := metrics.wt + 10
if (dx+w > game.width) {
dx := (game.width-w)
}
game.fillrectangle(dx,dy,w,30,0xFF000000)
game.drawrectangle(dx,dy,w,30,0xFFFFFFFF)
game.drawtext(this.tooltip,dx+5,dy,20,0xFFFFFFFF,"Arial")
}
}
}
;convert hsv values to rgb
HsvToRgb(h,s:=100,v:=100,alpha:=0xFF) {
h := mod(floor(h),360)
if (S>100 or S<0 or V>100 or V<0) {
msgbox % "The given HSV values (" h "," s "," v ") are not in valid range"
return 0
}
s := S/100
v := V/100
C := s*v
X := C*(1-abs(mod(H/60, 2)-1))
m := v-C
if (H >= 0 and H < 60) {
r := C, g := X, b := 0
} else if (H >= 60 and H < 120) {
r := X,g := C,b := 0
} else if (H >= 120 and H < 180) {
r := 0,g := C,b := X
} else if (H >= 180 and H < 240) {
r := 0,g := X,b := C
} else if (H >= 240 and H < 300) {
r := X,g := 0,b := C
} else {
r := C,g := 0,b := X
}
R := floor((r+m)*255)
G := floor((g+m)*255)
B := floor((b+m)*255)
return (alpha << 24) + (r<<16) + (g<<8) + b
}
f9::reload
f8::exitapp