|
Post by andrian on Dec 16, 2007 8:50:27 GMT -5
Does anybody have an algorithm to make a sprite go around another one? for example, in an RTS, if I select a unit and then tell it to go to a spot on the other side of, say a tree, then how can I make the unit go around the tree instead of walking through it or just stopping in front of it?
|
|
|
Post by DJLinux on Dec 16, 2007 9:13:46 GMT -5
|
|
|
Post by DJLinux on Dec 17, 2007 7:17:13 GMT -5
If the tutorial to havy for you here are the code. In a real game you don't need all the mouse drawing stuff important is GetPath/DrawPath. Joshy ' A* Pathfinder for andrian ' ' usage: ' left mouse button set PathStart (green) ' right mouse button set PathEnd (red) ' midle mouse button togle Walkable (blue)
struc VECTOR2D dim x,y end struc
struc COSTS dim f,g,h endstruc
struc CELL dim VECTOR2D Position dim VECTOR2D Array dim COSTS Cost dim State ' NONE / OPEN / CLOSED dim CELL &Parent dim Walkable ' True/False dim Index endstruc
struc DIRECTIONS dim VECTOR2D Add dim Cost,Flag end struc
struc TESTS dim Cost,Flag,x,y end struc
' cost,xadd,yadd,direction DataDirs: Data 1000, 0,-1, 1 ' north Data 1000, 1, 0, 2 ' east Data 1000, 0, 1, 4 ' south Data 1000,-1, 0, 8 ' west Data 1414, 1,-1, 3 ' north east Data 1414, 1, 1, 6 ' south east Data 1414,-1, 1,12 ' south west Data 1414,-1,-1, 9 ' north west
const _XCELLS=4*10,_YCELLS=3*10 const _LASTCELL=_XCELLS*_YCELLS-1 const _NONE =0,_OPEN=1,_CLOSED=2 const _HVCOST=1000,_DCOST=1414 ' int(SQRT(2)*1000)
dim CELL Terain(_LASTCELL) dim CELL &PathStart dim CELL &PathEnd dim CELL &Cell dim CELL &Parent dim CellWidth#,CellHeight# dim Index,CellIndex,NewCellIndex dim TESTS Test dim MustUpdate dim DIRECTIONS Dirs(7),DIndex,DirFlag
Gosub InitOpenGL2D Gosub InitTerain Gosub InitDirections
MustUpdate=True
' init any PathStart and PathEnd Index =int(_YCELLS*0.25)*_XCELLS+int(_XCELLS*0.25) &PathStart=&Terain(Index) Index =int(_YCELLS*0.75)*_XCELLS+int(_XCELLS*0.75) &PathEnd =&Terain(Index)
' draw a wall in center of the Terain Index =int(_YCELLS*0.1 )*_XCELLS+int(_XCELLS*0.5 ) while Index<int(_YCELLS*0.9 )*_XCELLS+int(_XCELLS*0.5 ) Terain(Index).Walkable=False:Index=Index+_XCELLS wend
' ' main loop ' while True if Mouse_Button(MOUSE_LBUTTON) then ' set new PathStart (green) Gosub GetNewCellIndex if NewCellIndex<>CellIndex then if &PathEnd<>&Terain(NewCellIndex) then CellIndex=NewCellIndex:&PathStart=&Terain(CellIndex) Terain(CellIndex).Walkable=True:MustUpdate=True endif endif elseif Mouse_Button(MOUSE_RBUTTON) then ' set new PathEnd (red) Gosub GetNewCellIndex if NewCellIndex<>CellIndex then if &PathStart<>&Terain(NewCellIndex) then CellIndex=NewCellIndex:&PathEnd=&Terain(CellIndex) Terain(CellIndex).Walkable=True:MustUpdate=True endif endif elseif Mouse_Button(MOUSE_MBUTTON) then ' make TerainCell as Walkable (blue) or not (rectangle) Gosub GetNewCellIndex if NewCellIndex<>CellIndex then if (&Terain(NewCellIndex)<>&PathStart) land (&Terain(NewCellIndex)<>&PathEnd) then CellIndex=NewCellIndex:MustUpdate=True Terain(CellIndex).Walkable= not Terain(CellIndex).Walkable endif endif endif
if MustUpdate=True then glClear(GL_COLOR_BUFFER_BIT) Gosub DrawTerain Gosub GetPath Gosub DrawPath MustUpdate=False SwapBuffers() else Sleep(10) endif wend
InitOpenGL2D: glMatrixMode (GL_PROJECTION) glLoadIdentity() glOrtho (0,WindowWidth(),WindowHeight(),0, 0,1) glMatrixMode (GL_MODELVIEW) glLoadIdentity() glDisable (GL_DEPTH_TEST) glDisable (GL_CULL_FACE) glMatrixMode (GL_MODELVIEW) CellWidth# =WindowWidth ()/_XCELLS CellHeight#=WindowHeight()/_YCELLS return
InitDirections: Reset DataDirs for DIndex=0 to 7 read Dirs(DIndex).Cost read Dirs(DIndex).Add.x read Dirs(DIndex).Add.y read Dirs(DIndex).Flag next return
InitTerain: ' get center of all TerainCells for Index=0 to _LASTCELL Terain(Index).Index = Index Terain(Index).Array.x = (Index % _XCELLS) Terain(Index).Array.y = (Index / _XCELLS) Terain(Index).Position.x = (CellWidth# *0.5)+Terain(Index).Array.x*CellWidth# Terain(Index).Position.y = (CellHeight#*0.5)+Terain(Index).Array.y*CellHeight# Terain(Index).Walkable = True next return
ClearTerain: ' clear all cost and set to STATE_NONE for Index=0 to _LASTCELL &Terain(Index).Parent = NULL Terain(Index).Cost.f = 0 Terain(Index).Cost.g = 0 Terain(Index).Cost.h = 0 Terain(Index).State = _NONE next return
DrawTerain: for Index=0 to _LASTCELL if &Terain(Index)=&PathStart then glColor3f(0,.75,0):Gosub DrawQuad elseif &Terain(Index)=&PathEnd then glColor3f(.75,0,0):Gosub DrawQuad elseif Terain(Index).Walkable=False then glColor3f(0,0,.75):Gosub DrawQuad endif glColor3f(.75,.75,.75):Gosub DrawRectangle next return
DrawPath: &Cell=&PathEnd while (&Cell.Parent<>NULL) if (&Cell<>&PathEnd) then Index=Cell.Index glColor3f(.75,.75,0):Gosub DrawDiamond endif &Cell=&Cell.Parent wend return
DrawQuad: glPushMatrix () glTranslatef (Terain(Index).Position.x,Terain(Index).Position.y, 0) glScalef (CellWidth#,CellHeight#, 1) glBegin (GL_QUADS) glVertex2f (-0.5, 0.5) glVertex2f (-0.5,-0.5) glVertex2f ( 0.5,-0.5) glVertex2f ( 0.5, 0.5) glEnd() glPopMatrix() return
DrawDiamond: glPushMatrix () glTranslatef (Terain(Index).Position.x,Terain(Index).Position.y, 0) glScalef (CellWidth#,CellHeight#, 1) glBegin (GL_QUADS) glVertex2f ( 0, 0.25) glVertex2f (-0.25, 0) glVertex2f ( 0,-0.25) glVertex2f ( 0.25, 0) glEnd() glPopMatrix() return
DrawRectangle: glPushMatrix() glTranslatef (Terain(Index).Position.x,Terain(Index).Position.y, 0) glScalef (CellWidth#,CellHeight#, 1) glBegin (GL_LINE_LOOP) glVertex2f (-0.5, 0.5) glVertex2f (-0.5,-0.5) glVertex2f ( 0.5,-0.5) glVertex2f ( 0.5, 0.5) glEnd() glPopMatrix() return GetNewCellIndex: ' get TerainCell from curent Mouse position NewCellIndex= int((Mouse_x()*WindowWidth() )/CellWidth#) NewCellIndex=NewCellIndex+int((Mouse_y()*WindowHeight())/CellHeight#)*_XCELLS return
GetMinCost: &Parent=NULL for Index=0 to _LASTCELL if Terain(Index).State=_OPEN then if &Parent=NULL then &Parent = &Terain(Index) elseif Terain(Index).Cost.F < Parent.Cost.F then &Parent = &Terain(Index) endif end if next return
TestNeighbour: Test.Flag=False if Test.X< 0 then return:endif if Test.X>=_XCELLS then return:endif if Test.Y< 0 then return:endif if Test.Y>=_YCELLS then return:endif Index=Test.X+Test.Y*_XCELLS
&Cell=&Terain(Index) if Cell.Walkable=False then return:endif if Cell.State<>_NONE then if (Parent.Cost.g+Test.Cost)<Cell.Cost.g then Cell.State=_NONE endif endif if Cell.State=_NONE then &Cell.Parent = &Parent Cell.State = _OPEN Cell.Cost.h = ABS(Cell.Position.x-PathEnd.Position.x)*_HVCOST Cell.Cost.h = Cell.Cost.h + ABS(Cell.Position.y-PathEnd.Position.y)*_HVCOST Cell.Cost.g = Parent.Cost.g + Test.Cost Cell.Cost.f = Cell.Cost.g + Cell.Cost.h endif Test.Flag=True return
TestNeighbours: DirFlag =0 For DIndex=0 to 7 Test.Cost=Dirs(DIndex).Cost Test.X=Parent.Array.x+Dirs(DIndex).Add.x Test.Y=Parent.Array.y+Dirs(DIndex).Add.y if DIndex<4 then Gosub TestNeighbour if Test.Flag=True then DirFlag=DirFlag or Dirs(DIndex).Flag endif else if (DirFlag and Dirs(DIndex).Flag)=Dirs(DIndex).Flag then Gosub TestNeighbour endif endif next return
GetPath: ' Calc a Path between PathEnd and PathStart Gosub ClearTerain PathStart.State=_OPEN Do Gosub GetMinCost if (&Parent=NULL) lor (&Parent=&PathEnd) then return:endif Parent.State=_CLOSED Gosub TestNeighbours Loop return
|
|
|
Post by Empyrion Martyr on Dec 30, 2007 10:30:32 GMT -5
hey i did a b4gel library with a* and it's pretty easy to use, check it out... basic4gl.proboards20.com/index.cgi?board=demo&action=display&thread=1181825983and this is the place to download it basic4gl.wikispaces.com/space/showimage/pathfinding_1.1.zipyou only need to include it, set the cells as unwalkable (those that are) and call a gosub Pathfind... the path is included inside a vector The lib has some advanced features besides the simple find-a-path-and-give-it-to-me and i'm planning on adding more soon, but i'd be happy to see where it ends up if some one else uses it All the help files and examples are inside (i'm coding and rts now so i needed such a lib) I guarantee it is easy to use just check the examples ----------------------- Joshy it would be nice if you timed the algorithm (it's supposed to be used in a RTS)
|
|
|
Post by socomsniperaj on Jan 25, 2008 20:11:14 GMT -5
Could someone please explain how djlinux's program works? I know how the path finding aspect works but I have no idea how there are a variable number of path elements. Or are there a certain number which it can't reach based upon grid size? I've tried breaking it down but can't figure it out.
Please help, SSAJ
|
|
|
Post by DJLinux on Jan 25, 2008 20:54:15 GMT -5
Every cell with Cell.Walkable=True in the grid can act as a path element.
I hope my answer is what you asked for (if not ask again)
Joshy
|
|
|
Post by socomsniperaj on Jan 25, 2008 21:12:04 GMT -5
No, that isn't what I meant. What I meant was that I don't know how you have it change from the start cell to a new cell in the path. Continuing along until the end. How does it have a variable number of cells in the path, or does it not. So that there is a max path length? I guess that still isn't quite clear, I could get one to change from one cell to the next but with my version there are a fixed number of elements in the path just not all are always used. So is there a way to make a new element every time it needs to so there are a variable number of elements. Edit: Actually I would need special code to go from one element to the next which would take a lot of time and space, so I need to know how to do that to. Perhaps understanding pointers better would help me. Thanks for the info so far. SSAJ
|
|
|
Post by DJLinux on Jan 25, 2008 21:23:33 GMT -5
In DrawPath: you can see it is a chain from PathEnd over PathEnd.Parent ... Parent.Parent ... to PathEnd It's not an array like PathElements(max_elemets) it used pointers one Path Element points to the next and ends if the last Element.Parent=NULL = PathEnd
sorry if i don't understand you right (It's my bad english)
Joshy
|
|
|
Post by socomsniperaj on Jan 25, 2008 22:03:53 GMT -5
So there is a structure inside of a structure etc. etc.? So theres a start cell with data and inside that there is cell, with the same data as it's parent then the same repeated as needed? If not that gave me a wonderful idea if it works. Edit: I think what I just said is wrong. I looked at it some more and it looks like theres an array of all possible path elements and each one is a structure to hold the cells data. Along with a pointer pointing to the cell before it. Is that right? Thanks for the help, SSAJ P.S. Your English is fine
|
|
|
Post by Empyrion Martyr on Jan 27, 2008 10:23:03 GMT -5
yes socom, it's a tree, the cell field named "parent" is a CELL pointer to another CELL. It is not actually a structure inside a structure, it is a pointer of CELL type. The topmost cell has no parent, thus the test [CELL_NUMBER].parent=NULL will give TRUE for that one (thats how you know when to stop when constructing the final path).
In fact it's a nice and probably the easiest way to do A* in b4gel. (and is also fast)
|
|