Pathing
Blitz3D Forums/Blitz3D Beginners Area/Pathing
| ||
| (Edited) Can anyone offer any suggestions of how to proceed from here? . Code removed, No longer relevant.. See below. |
| ||
| the idea is that each time you choose one of the other node connected to the current node, the other node has a field "discoveredfromnodeid" (index or handle) and when you reach the destination node, you can then use this discoveredfromnodeid to retrieve the node connected to this node which is part of the path until you reach the start node... |
| ||
| I have no idea what you mean by "node" or 'connections', please can you elaborate on how to implement this in the code I have provided? ___ also, further to the initial post, I realise I need nothing so complex as AStar, since the algorithm need only to determine that a path between two points is POSSIBLE (i.e. found within a set number of iterations, perhaps?) not necessarily to determine the most eficient path. |
| ||
| i am talking about the astar logic in my previous post, not sure if this is what you want... personally i prefer to explain the concepts in words and then you can implement it as you prefer in code. in the system that i use there are nodes, each node being a 2d point (in a 2d space) or a 3d point (in a 3d space), and each node having one or several links to others nodes (not necessarily positionned on a grid, but they can be, but it is not a requirement). see : rd-stuff.fr/HQSM-autocreatenodes-autocreatelinks-FBLR.png (nodes positionned on a grid with 4 links per node) rd-stuff.fr/HQSM-autocreatenodes-autocreatelinks-FBLRFLFRBLBR.png (nodes positionned on a grid with 8 links per node) rd-stuff.fr/autocreate-nodes-then-autocreate-links-640x480-10fps-HQ.gif (nodes positionned around obstacles, with up to 20 links per node) then there is a start node (nearest reachable to the entity which must find a path to the target) and a destination node (nearest reachable to the entity which is the target) then using the astar logic, starting at the startnode, all nodes connected to this node are analyzed, and depending the total "fly distance", the next best node is chosen, then the process repeat until you reach the target node or until all nodes have been considered. the discoveredfromnodeid is used to be able to go backward to a node which has links to nodes which have not been considered yet, and also after the target node is reached, to go backward on the path to determine which nodes are parts of the path. then you can reverse the order of the nodes parts of the path to make your entity follow the path (go from one node to the next node) (note that you can find several examples in the code archives, if you are curious) |
| ||
| So since as mentioned AStar is way above anbd beyond what I need, I created a filling algorithm that serves the purpose of spreading out to identify if there is a path at all. It needs some optimisation, this is just thrown together for sake of example, but the essentials are there. It's also very much slowed by the visuals so this can be ignored for consideration of actual use. I previously tried to have two "simultaneous" searches, one originating from the target, since this could speed up the process but it didn't work too well - I was not able to get this to check simultaneously. I'm assuming from the get-go it will require a duplicate of the custom Type and its own map constant (TESTED_FROM and TESTED_TO for example) and then PATH_DOISCOVERED can be set to true if the From Test hits a TESTED_TO location or a To Test hits a TESTED_FROM location.... anyway, it's at least working from one side for now, so that's something, but if anyone has suggestions on the improvement, I'd really welcome it. Thanks.
Const MAPSIZEX=64
Const MAPSIZEY=64
Const VISUAL_SCALE_X=16
Const VISUAL_SCALE_Y=12
Global PATH_DISCOVERED
Type Cells
Field X
Field Y
End Type
Const NOTHING=0
Const WALL=1
Const TESTED=2
Dim MAP(MAPSIZEX-1,MAPSIZEY-1)
Dim TESTMAP(MAPSIZEX-1,MAPSIZEY-1)
Global ARBITRARYSTARTX=MAPSIZEX*0.5
Global ARBITRARYSTARTY=MAPSIZEY*0.5
Global ARBITRARYENDX
Global ARBITRARYENDY
Initialise
Function Initialise()
Graphics 1024,768,32,2
SetBuffer BackBuffer()
SeedRnd MilliSecs()
InitialiseRandomMap()
InitialiseTestParams
If (Testing())
RuntimeError("Path was discovered")
Else
RuntimeError("Path was not discovered")
End If
End Function
Function InitialiseRandomMap()
Local Iterations
For Iterations=1 To 2000
Local X=Rand(0,MAPSIZEX-1)
Local Y=Rand(0,MAPSIZEY-1)
MAP(X,Y)=WALL
Next
End Function
Function VisualExample()
Cls
Local X
Local Y
For Y= 0 To MAPSIZEY-1
For X= 0 To MAPSIZEX-1
Local m=(TESTMAP(X,Y))
Select m
Case WALL:
Color 255,255,255
Rect X*VISUAL_SCALE_X,Y*VISUAL_SCALE_Y,VISUAL_SCALE_X,VISUAL_SCALE_Y,True
Case TESTED:
Color 0,255,0
Rect X*VISUAL_SCALE_X,Y*VISUAL_SCALE_Y,VISUAL_SCALE_X,VISUAL_SCALE_Y,True
Default :
;Case NOTHING
End Select
Next
Next
Color 0,0,255
Oval ARBITRARYSTARTX*VISUAL_SCALE_X,ARBITRARYSTARTY*VISUAL_SCALE_Y,VISUAL_SCALE_X,VISUAL_SCALE_Y,True
Color 255,0,0
Oval ARBITRARYENDX*VISUAL_SCALE_X,ARBITRARYENDY*VISUAL_SCALE_Y,VISUAL_SCALE_X,VISUAL_SCALE_Y,True
Flip
End Function
Function Testing()
Repeat
Local Count=0
Local CT.Cells
For CT = Each Cells
If (CT<>Null)
Count=Count+1
TestCells(CT\X,CT\Y)
Delete CT
End If
Next
If (Not(Count))
Return PATH_DISCOVERED
End If
Forever
End Function
Function TestCells(X,Y)
Local XX
Local YY
Local XT
Local YT
For YY=Y-1 To Y+1
For XX=X-1 To X+1
If (YY<>Y) And (XX<>X)
; Diagonals go here. We don't want diagonals so this is empty.
Else
YT=(MAPSIZEY+YY) Mod MAPSIZEY
XT=(MAPSIZEX+XX) Mod MAPSIZEX
Local m= TESTMAP(XT,YT)
If ((XT=ARBITRARYENDX) And (YT=ARBITRARYENDY))
PATH_DISCOVERED=True
Exit
Else
If (m=NOTHING)
TESTMAP(XT,YT)=TESTED
AddForTesting(XT,YT)
End If
End If
End If
;_____________________________________________________________________________
VisualExample
;_____________________________________________________________________________
Next
Next
If (PATH_DISCOVERED) Then Delete Each Cells
End Function
Function InitialiseTestParams()
Dim TESTMAP(MAPSIZEX-1,MAPSIZEY-1)
Local X
Local Y
For Y=0 To MAPSIZEY-1
For X=0 To MAPSIZEX-1
If (MAP(X,Y)=WALL) Then TESTMAP(X,Y)=WALL
Next
Next
ARBITRARYENDX=Rand(0,MAPSIZEX-1)
ARBITRARYENDY=Rand(0,MAPSIZEY-1)
AddForTesting(ARBITRARYSTARTX,ARBITRARYSTARTY)
End Function
Function AddForTesting(X,Y)
Local C.Cells=New Cells
C\X=X
C\Y=Y
End Function
|
| ||
| @_PJ_>>interesting method and code, thanks for sharing. |
| ||
| It's probably not ideal for any purpose. As a pixel fill routine it could be expanded upon to define areas or lines (at the very least along one dimension) rather than individual unit locations) but overall I suspect it's rather trite and unwieldy. Certainly not a "clever" algorithm, It is a basic simple programmatically less complex form that could determine whether an existing path exists between the two points. Incidentally, for my purposes I required it wraparound horizontally and that diagonals are not counted as valid "steps" so these are possible areas where any more general implementation may be critical. As stated above, the most logical improvement would be to have an equivalent fill spreading out from the target towards the entity simultaneously and the intersection of these would indicate a valid path - however when I tried this it didn't quite function as intended so I removed all that. This is really where I need help. ___ Finally I'm not happy with a Repeat/Forever - although it SHOULD always exit as soon as there are no more locations left to test - but again, this is more a simplified version for the sake of the example. Even a simple "insanity check" (i.e. limit number of iterations to MAPSIZEX * MAPSIZEY) rather than Repeat/Forever ... |
| ||
| You should go with A*, it's simple to understand and quite fast. Also you can skip diagonals and wrap the map if you want. |
| ||
| [/quote] You should go with A*, it's simple to understand and quite fast. Also you can skip diagonals and wrap the map if you want. [/quote] Please explain how A* is advantageous to the simple determination of whether a path exists or not? Also not sure if it's any faster since with A*, at each point calculations based on the distance and weighting factors , whereas here a valid location is determined by its nature with no dependency on any relationship to the target. Given your suggestions, an example of an A* routine that incorporates solutions by wraparound would be most welcome. Thanks so much for your help! |
| ||
| You can probably add some Astar logic in your logic : instead of giving the same priority to all cells which are put in the list to analyze, each time you find a new cell (a neighbor of a cell you have analyzed), calculate its "path distance" (the number of cells it takes to reach this cell from the start cell) from the start cell and its "fly distance" (the number of cells it takes to reach the end cell from this cell) to the end cell, then add those 2 distances together in a "total distance". Then reorganize your list of totals by distance (from low to high), then the next best cell to analyze will be the one which has not been processed yet (its neighbors cells have not been analyzed yet) and which has the lowest total distance. That's the idea of astar... |
| ||
| You can probably add some Astar logic in your logic : instead of giving the same priority to all cells which are put in the list to analyze, each time you find a new cell (a neighbor of a cell you have analyzed), calculate its "path distance" (the number of cells it takes to reach this cell from the start cell) from the start cell and its "fly distance" (the number of cells it takes to reach the end cell from this cell) to the end cell, then add those 2 distances together in a "total distance". Then reorganize your list of totals by distance (from low to high), then the next best cell to analyze will be the one which has not been processed yet (its neighbors cells have not been analyzed yet) and which has the lowest total distance. That's the idea of astar... I don't see the point, all will be processed eventually or the path will be found. Spending time re-ordering for what purpose? As I understand it, this is all to determine the best route which is of no relevance whatsoever here. Consider situations where no route exists. What benefit is gained in reordering the priorities??? I do not see at all the relevance of distance. For a point X,Y then (for example) X-1,Y and X+1,Y may be equally closer or further away from a route to the target. Given the convoluted nature of the maze, and the possibility (I had one earlier in which there was a single route that necessitated the wraparound from a single gap) of wraparound makes the notion of any test location's distance to either the target or from the origin rather moot. In cases where there is a single, but highly complex convoluted route, then it's very likely the "cell distance" required is very large. |
| ||
| If you use A* with no diagonals, you will use Manhattan distance heuristic, wich is the fastest to compute (it uses only addition). But you're right, if there is no path, every contiguous cell will be processed anyway, and you'll have no gain. One trick for that is to determine from wich point the algorithm must start, sometimes it's better to start from the end... Faster than A* is Jump Point Search (wich is A* anyway, but modified), but it only works on 2d uniform grids while A* works for everything. It would work for your example, and would be very fast, but it's more complicated than A* to implement. |
| ||
| all will be processed eventually or the path will be found. Spending time re-ordering for what purpose? No the logic of astar is to analyze in priority the cells which have the shortest total distance (path distance from the start cell to this cell + fly distance from this cell to the end cell) so not all cells will be analyzed, and in many cases only the cells in direction of the end cell will be analyzed, unlike your method where cells are analyzed in all directions... The reordering of cells to process by total distance (from lowest to highest) is to analyze in priority the cells which are the shortest potential path to the end cell and therefore most likely to reach the path (not always the case but often) Your method searches in all directions so it will process more cells... The distance is not really a distance in your case, it is rather the number of cells from the start cell to this cell and the numbers of cell (at up or at down and at left or at right) from this cell to the end cell. A real distance is used when you use nodes (not necessarily positioned on a grid) (i use nodes positioned on a grid or positioned around obstacles (with links between some nodes)) |
| ||
| You make an assumption that "the shortest potential path to the end cell and therefore most likely to reach the path " And anyway, neither has anything to do with the reason for posting and the point I made clear in Post 5, but clearly had to repeat in #7 which is still ignored... I previously tried to have two "simultaneous" searches, one originating from the target, since this could speed up the process but it didn't work too well - I was not able to get this to check simultaneously. it will require a duplicate of the custom Type and its own map constant (TESTED_FROM and TESTED_TO for example) and then PATH_DOISCOVERED can be set to true if the From Test hits a TESTED_TO location or a To Test hits a TESTED_FROM location.... anyway, it's at least working from one side for now, so that's something, but if anyone has suggestions on the improvement, I'd really welcome it. Thanks. As stated above, the most logical improvement would be to have an equivalent fill spreading out from the target towards the entity simultaneously and the intersection of these would indicate a valid path - however when I tried this it didn't quite function as intended so I removed all that. This is really where I need help. One trick for that is to determine from which point the algorithm must start, sometimes it's better to start from the end... Yes. I am aware which is why I had already tried to maximise this by a simultaneous search from both - which is where I had difficulty and so I posted here for help with that particular issue as explained in numerous posts but you do not seem to offer anything particular in relation to this as was asked. |
| ||
| I didn't understand what you were looking for... It's not pathfinding but checking for contiguous cells like a fill algorithm, this way yes it's faster than A*... I wrote an example and it seems to be the same kind of code that you wrote : (you need a level image, white is walkable, black are walls, use mousehit left&right to set the start and end points, and spacebar to draw the fill progress until it reaches the end point) Simultaneous search from start and end point would make the thing faster when there is no path, when one of those point is "enclosed" in a small area. I'll try on my example. |
| ||
| Thank you. I appreciate you taking the time. The reason why my previous attempt failed was mainly because I had the DESTINATION fill placed procedurally AFTER the SOURCE fill, te intent was I think to populate a list of those available cells for testing areound the current test cell but of course the 'list' of types is always growing as populating the list of available cells adds them to the list of cells currently iterated. Since one cannot simulatneously have expanding For/Each lists I think I need to contain one within the other (NOT simply nested) but perhaps where one is iterated through only by one instance whilst the otehr iteration is ongoing: For example:
Local OtherIteration.OtherCells=First OtherCells
Local CT.Cells
For CT = Each Cells
If (CT<>Null)
Count=Count+1
TestCells(CT\X,CT\Y)
Delete CT
End If
If (OtherIteration<>Null)
TestOtherCells
OtherIteration = OtherCells After OtherIteration
End If
Next
Although the syntax for the type iteration might not be accurate above. |
| ||
| Okay so I allow for the iteration of the 'End' cells to be performed within the main cell iteration loops so that the checks can be performed from "both ends" 'simultaneously' The final step was to incorporate tracking of the number of datapoints checked for and identified (I did this through a bitwise method so for simplicity's sake, only 31 (1 reserved for link to origin) individual datapoints may be checked) and settting the datapoints to have unique test-cell origins and any time such test cells 'meet' others, the tracking information is shared: (Simplified to just 8 bits) 1 DP "A" is used as origin with bitwise code 0000 0001 2 DP "B" is used as origin with bitwise code 0000 0010 3 DP "C" is used as origin with bitwise code 0000 0100 4 DP "D" is used as origin with bitwise code 0000 1000 'TO' Checks commence from X1,Y1 with default code 1000 0000 'FROM' Checks commence from XA,YA with code 0000 0001 'FROM' Checks commence from XB,YB with code 0000 0010 'FROM' Checks commence from XC,YC with code 0000 0100 'FROM' Checks commence from XD,YD with code 0000 1000 TOCHECK Encounters a cell checked by A with code 0000 0001 TOChecks value is now 1000 0001 A checks now 1000 0001 C checks encounter cells checked by D C check values now given 0000 1100 D check values now given 0000 1100 So if A should now meet C or D, the values for A, C, D AND the checks originating from the START are: 1000 1101 1000 1101 It can be easy to see by the presence of individual bits whether valid paths are present either between datapoints or the 'start'. ________ Thanks for all your help :) |
   |