Diddy's Pathfinding

Monkey Forums/Monkey Programming/Diddy's Pathfinding

c.k.(Posted 2012) [#1]
I've got a 2-dimensional tile maze. Can diddy find me the path through there? I'd also like to get 1) the number of steps in the final path (since it's a tile maze, how many blocks are in the path), and 2) the number of turns in the final path.


Gerry Quinn(Posted 2012) [#2]
Well, Diddy has a pathfinding algorithm, so presumably it can (I haven't tried it).

You need to get your maze into its format, then ask it for a route from start to finish. By inspecting the resulting route you then can answer your other questions.


Rushino(Posted 2012) [#3]
Hi,

I was exploring a lots how A* work.. and ive looked at how diddy pathfinding looking. There no real format except a standard x,y cols array. Just 'mirror' your maze into this format (If its what gerry meant) and the paths are stored inside a variable like this.. x1,y1,x2,y2,x3,y3,... so:

1- The number of steps is easy to find, just get the var where the path are virtually stored then its Lenght / 2 and you get the number of moves.
2- It can't get you the number of turns that would require a bit more programming or you could also compare the moves like compare what changed from x1,y1 to x2,y2 and then figure out there was a turn.


Gerry Quinn(Posted 2012) [#4]
Yes, that's what I meant. Inspect the path to count the turns. Just run through the steps from beginning to end, determining if they are horizontal or vertical - and if the current step is a different direction from the last one, add 1 to the number of turns.


Rushino(Posted 2012) [#5]
Your explanation was better. lol English isnt my first language.


Xaron(Posted 2012) [#6]
I've implemented A* pathfinding for a hexagonal grid. I can post that if anyone is interested?


therevills(Posted 2012) [#7]
I can post that if anyone is interested?

Please do :)


Xaron(Posted 2012) [#8]
Well here it is. Please note, this one is for hexagonal grids which I have that way in my 2d arrays:

'That's for even y lines (the middle one to know how to access the neighbors!)
'-------------             | 0,1 | 1,1 |
'| 0,1 | 1,1 |            / \   / \   / \
'-------------------     /   \ /   \ /   \
'| 0,2 | 1,2 | 2,2 |    | 0,2 | 1,2 | 2,2 |
'-------------------     \   / \   / \   /
'| 0,3 | 1,3 |            \ /   \ /   \ /
'-------------             | 0,3 | 1,3 |


'That's for odd y lines (the middle one to know how to access the neighbors!)
'      -------------       | 1,0 | 2,0 |
'      | 1,0 | 2,0 |      / \   / \   / \
'-------------------     /   \ /   \ /   \
'| 0,1 | 1,1 | 2,1 |    | 0,1 | 1,1 | 2,1 |
'-------------------     \   / \   / \   /
'      | 1,2 | 2,2 |      \ /   \ /   \ /
'      -------------       | 1,2 | 2,2 |


The hexagonal A* pathfinding is more complex than the "normal" one for classic 2d arrays. You should be able to easily simplify the code. If not I'll do that. ;)

Part I: the central part, the path finder from my game Warhex (which isn't finished yet):

Screw the includes, you won't need it. I just call findpath where I use units as parameters but use only the x and y coordinates here, so that won't be a problem to use it for your own purposes.
There's still some other stuff in it here (especially in the function walkable) but you should be able to sort out that as well. If not just ask, I'm glad to help!




Gerry Quinn(Posted 2012) [#9]
I must admit, I've always found the simple Dijkstra algorithm adequate for my needs.

With classic narrow-corridor mazes etc., it's probably faster too. In a good maze, heuristics shouldn't work in which case the A* is just overhead.


maltic(Posted 2012) [#10]
@Gerry Quinn
You may as well just use a breadth first search if you don't have edge weights. That will have even less overhead. In fact its asymptotically better (O(V+E) vs O((E+V)lg V) assuming a binary heap)

In fact, if all you want is ANY path in a maze from some starting location to some finishing location, with no edge weights. A depth first search will be the absolute fastest algorithm possible. It has the same time complexity as BFS (O(V+E)) however the space complexity of DFS is O(n) where n is the length of the longest possible path, whereas in BFS the space complexity is O(b^d) where b is the branching factor and d is the depth of the first solution. The fact that DFS uses less space in the average case, and the fact that the most recent vertex is the top of the stack, makes it faster due to better cache usage.


Gerry Quinn(Posted 2012) [#11]
Breadth-first is what I understand by the Dijkstra algorithm. I.e. you expand from a start location marked '1', marking all unmarked squares adjacent to a '1' with '2' and so on. If you stop when you reach the target, I would call that a breadth-first search.

You can also have a couple of variations:

(1) You can expand to a fixed distance if you have no particular target, or multiple targets in mind.

(2) If movement is symmetrical as well as unweighted, you can expand from the target location instead. This could be useful if you have (say) a roguelike in which many monsters are trying to find a path to a single player character. Though in practice, you would probably be hard-pressed to find a situation in which this optimisation would be necessary these days, and you also have to be careful if moving objects cannot pass over each other, because the map will change when one of the monsters moves. However this can also create an interesting form of artificial stupidity, where monsters tend to block one other in a semi-consistent way.

[I'm making a roguelike at the moment, so these things are on my mind. In practice, at the moment I'm using plain Dijkstra for each monster that is within a reasonable range of the player character.]


Curlew Eskimo(Posted 2014) [#12]
Thanks Xaron,

Curlew Eskimo