I'm back with pathfinding!

Blitz3D Forums/Blitz3D Programming/I'm back with pathfinding!

psychicbottle (Posted 2013) [#1]

Hey all, I don't know if anyone remembers me (it's been almost 9 months since my last post!) I come bearing code and questions! Recently I have been dabbling with some C++,Python,Ruby,Java,Assembly, ect. (everything) but I found that prototyping ideas in these languages was difficult for me and I wanted to come back to blitz to rough out some game concepts and some pathfinding. Last night I began attempt three of week one on pathfinding, I actually Managed it! now I know my code is shotty and the algorithm is probably screwed up but I wasn't looking for anything great just.. usable. I was hoping to have maybe 5 people path-finding with my library however... it's way too slow for one. I can see slow places in my code (mainly in the logic functions) but I don't know how to work around them. any help is appreciated and thanks in advance! :) (save image as map.bmp) Graphics 600, 600, 32, 2 SetBuffer BackBuffer() mapSizeX = 30 mapSizeY = 30 cellSizeX = GraphicsWidth()/mapSizeX cellSizeY = GraphicsHeight()/mapSizeY startNode = 80 ;cell to search from endNode = 198;cell to search to Global finished, path Dim open_list(mapSizeX*MapSizeY) Dim closed_list(mapSizeX*MapSizeY) ;initiate Const OPEN = 1 Const CLOSED = 2 Const NONE = 0 Const FILLED = 1 Const EMPTY = 0 Type nodeType Field F, G, H Field Parent, list = NONE, EP Field ID, x, y Field walkable = False End Type mapPic = LoadImage("map.bmp") DrawImage mapPic, 0, 0 i = 0 For x = 0 To mapSizeX -1 ;loops through rows For y = 0 To mapSizeY -1 ;loops thorugh collumns node.nodeType = New nodeType i = i + 1 node\x = x ;sets the X placement on the map node\y = y ;sets the Y placement on the map node\id = i ;gives the new node an ID node\list = NONE GetColor(x,y) If ColorRed() = 0 And ColorGreen() = 0 And ColorBlue = 0 Then node\walkable = False Else node\walkable = True EndIf If ColorRed() = 255 And ColorGreen() = 0 And ColorBlue() = 0 Then endNode = i EndIf If ColorRed() = 0 And ColorGreen() = 255 And ColorBlue() = 0 Then startNode = i EndIf Next Next For x = 0 To mapSizeX-1 For y = 0 To mapSizeY-1 For node.nodeType = Each nodeType If node\id = endNode Then endNodeX = node\x endNodeY = node\y EndIf Next Next Next For x = 0 To mapSizeX-1 For y = 0 To mapSizeY-1 For node.nodeType = Each nodeType If node\x = x And node\y = y Then node\H = Abs(endNodeX - x) + Abs(endNodeY - y) DebugLog "ID: " + node\id + ", H: " + node\H DebugLog "ENDX: " + endNodeX + " ENDY: " + endNodeY DebugLog "X: " + x + " Y: " + y EndIf Next Next Next fntArial=LoadFont("Arial",10) ;load font Global fatherNode = startNode ; sets the first checked node as the starting node While finished = False render(fntArial, mapSizeX, mapSizeY, cellSizeX, cellSizeY, startNode, endNode) logic(mapSizeX, mapSizeY, cellSizeX, cellSizeY, startNode, endNode) While KeyDown(57) Wend Wend For node.nodeType = Each nodeType If node\H = 0 And node\list = CLOSED Then path = node\parent node\EP = True pathing = True EndIf Next While pathing = True For node.nodeType = Each nodeType If node\id = path And node\list = CLOSED Then node\EP = True path = node\parent DebugLog "ID: " + node\id DebugLog "PARENT: " + node\parent If node\G = 0 Then DebugLog "GOTITTTTTTTT!!!!" pathing = False EndIf EndIf Next Wend While Not KeyHit(1) ;Main Loop Cls renderPath(fntArial, mapSizeX, mapSizeY, cellSizeX, cellSizeY, startNode, endNode) Flip Wend ;end "while" loop End ;end program Function tracePath(path) For x = 0 To mapSizeX-1 For y = 0 To mapSizeY-1 For node.nodeType = Each nodeType If node\id = path And node\x = x And node\y = y Then node\EP = True path = node\parent Return path EndIf Next Next Next End Function Function renderPath(fntArial, mapSizeX, mapSizeY, cellSizeX, cellSizeY, startNode, endNode) Color(80,15,90) Rect(0, 0, GraphicsWidth(), GraphicsHeight(), 1) For x = 0 To mapSizeX-1 For y = 0 To mapSizeY-1 For node.nodeType = Each nodeType If node\x = x And node\y = y ;checks to see if this is the node with the correct coords If node\walkable = False Then ;checks to see if you cannot walk over this node Color(130,45,175) Rect(x * cellSizeX ,y * cellSizeY ,cellSizeX ,cellSizeY , 1) EndIf If node\walkable = True Then ;Checks to see if you can walk over this node Color(45,0,0) Rect(x * cellSizeX ,y * cellSizeY ,cellSizeX ,cellSizeY , 1) EndIf If node\list = OPEN Then ;Checks to see if this is the node you are checking Color(30,90,0) Rect(x * cellSizeX ,y * cellSizeY ,cellSizeX ,cellSizeY , 1) EndIf If node\id = startNode Then ;Checks to see if this is the node you are checking Color(30,130,30) Oval(x * cellSizeX ,y * cellSizeY ,cellSizeX ,cellSizeY , 1) ;draws an indicator for the start node EndIf If node\id = endNode Then ;Checks to see if this is the node you are checking Color(250,180,30) Oval(x * cellSizeX ,y * cellSizeY ,cellSizeX ,cellSizeY , 1) ;draws an indicator for the start node EndIf If node\EP = True Then Color(255,0,0) Oval(x * cellSizeX + cellSizeX/4 ,y * cellSizeY + cellSizeY/4 ,cellSizeX/2 ,cellSizeY/2 , 1) ;draws an indicator for the start node EndIf Color(0,255,0) ;F Text x * cellSizeX + (cellSizeX/2), y * cellSizeY + (cellSizeY/2), node\id EndIf Next Next Next End Function ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;RENDER FUNCTIONS HERE Function render(fntArial, mapSizeX, mapSizeY, cellSizeX, cellSizeY, startNode, endNode) Cls renderNodes(fntArial, mapSizeX, mapSizeY, cellSizeX, cellSizeY, startNode, endNode) Flip End Function Function renderNodes(fntArial, mapSizeX, mapSizeY, cellSizeX, cellSizeY, startNode, endNode) Color(80,15,90) Rect(0, 0, GraphicsWidth(), GraphicsHeight(), 1) For x = 0 To mapSizeX-1 For y = 0 To mapSizeY-1 For node.nodeType = Each nodeType If node\x = x And node\y = y If node\walkable = False Then ;checks to see if you cannot walk over this node Color(130,45,175) Rect(x * cellSizeX ,y * cellSizeY ,cellSizeX ,cellSizeY , 1) EndIf If node\walkable = True Then ;Checks to see if you can walk over this node Color(45,0,0) Rect(x * cellSizeX ,y * cellSizeY ,cellSizeX ,cellSizeY , 1) EndIf If node\list = OPEN Then ;Checks to see if this is the node you are checking Color(30,90,0) Rect(x * cellSizeX ,y * cellSizeY ,cellSizeX ,cellSizeY , 1) EndIf If node\id = startNode Then ;Checks to see if this is the node you are checking Color(30,130,30) Oval(x * cellSizeX ,y * cellSizeY ,cellSizeX ,cellSizeY , 1) ;draws an indicator for the start node EndIf If node\id = endNode Then ;Checks to see if this is the node you are checking Color(250,180,30) Oval(x * cellSizeX ,y * cellSizeY ,cellSizeX ,cellSizeY , 1) ;draws an indicator for the start node EndIf If node\list = CLOSED Then ;Checks to see if this is the node you are checking ;Color(30,90,150) ;Oval(x * cellSizeX + cellSizeX/4 ,y * cellSizeY + cellSizeY/4 ,cellSizeX/2 ,cellSizeY/2 , 1) ;draws an indicator for the start node EndIf If node\EP = True Then Oval(x * cellSizeX + cellSizeX/4 ,y * cellSizeY + cellSizeY/4 ,cellSizeX/2 ,cellSizeY/2 , 1) ;draws an indicator for the start node EndIf EndIf Next Next Next End Function ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;LOGIC FUNCTIONS BELOW Function logic(mapSizeX, mapSizeY, cellSizeX, cellSizeY, startNode, endNode) For x = 0 To mapSizeX-1 For y = 0 To mapSizeY-1 For node.nodeType = Each nodeType If node\x = x And node\y = y And node\id = fatherNode fatherNodeX = x fatherNodeY = y fatherNodeG = node\G node\list = CLOSED closed_list(node\id) = FILLED EndIf Next Next Next For x = 0 To mapSizeX-1 For y = 0 To mapSizeY-1 For node.nodeType = Each nodeType If node\walkable = True Then If node\list = CLOSED And node\H = 0 Then finished = True If node\x = fatherNodeX And node\y = fatherNodeY -1 And node\list = NONE Then ;Checks to see if this node is above the FatherNode node\list = OPEN open_list(node\id) = FILLED node\parent = fatherNode node\G = movementCalc(fatherNodeG) EndIf If node\x = fatherNodeX And node\y = fatherNodeY +1 And node\list = NONE Then ;Checks to see if this node is below the FatherNode node\list = OPEN open_list(node\id) = FILLED node\parent = fatherNode node\G = movementCalc(fatherNodeG) EndIf If node\x = fatherNodeX +1 And node\y = fatherNodeY And node\list = NONE Then ;Checks to see if this node is right to the FatherNode node\list = OPEN open_list(node\id) = FILLED node\parent = fatherNode node\G = movementCalc(fatherNodeG) EndIf If node\x = fatherNodeX -1 And node\y = fatherNodeY And node\list = NONE Then ;Checks to see if this node is right to the FatherNode node\list = OPEN open_list(node\id) = FILLED node\parent = fatherNode node\G = movementCalc(fatherNodeG) EndIf EndIf Next Next Next For x = 0 To mapSizeX-1 For y = 0 To mapSizeY-1 For node.nodeType = Each nodeType If node\x = x And node\y = y And node\list = OPEN Then node\F = node\G + node\H EndIf Next Next Next fatherNode = nextStep(mapSizeX, mapSizeY) End Function Function movementCalc(fatherNodeG) G = fatherNodeG + 10 Return G End Function Function nextStep(mapSizeX, mapSizeY) newFatherValue = 10000 For x = 0 To mapSizeX-1 For y = 0 To mapSizeY-1 For node.nodeType = Each nodeType If node\x = x And node\y = y And node\list = OPEN And node\F <= newFatherValue Then newFatherValue = node\F newFather = node\id EndIf Next Next Next Return newFather End Function [img scontent-b.xx.fbcdn.net/hphotos-ash4/1394458_589059784483645_536316358_n.jpg]