Manhattan pathfinding code

Does anyone have an example of Manhattan pathfinding code in Xojo? I’ve been reading everything I can about it in general, but not knowing any other language is making is hard to figure out.

This is my scenario and how I’m thinking of approaching it, but would appreciate coments so I don’t chase the wrong rabbit here.

I’ve got a grid that is 9x9. It’s on a custom canvas object which has a property of Tiles(). They run from left to right, top to bottom by Index. So, the upper left “tile” has an index of 0 and the bottom right an index of 80.

I need to determine if there is an open path from a given tile to another. I don’t really need the shortest route, though it looks like this is what MAnhattan code would return. I just need to know if there is a path, or if the two tile are “walled off” from each other. Manhattan, because I’m not allowing diagonal moves.

So, my likely not straightforward ay of doing this is to give each tile an X and a Y integer property like tile(0).iXindex = 0, …iYindex = 0, tile(8).iXindex = 8, …iYindex = 0 and so on.

Then use those properties to write the functions for a Manhattan algorithm.

Does this seem like a good approach? Or is there something much better that I should be doing?

EDIT TO ADD: Also, I’m trying to turn the code from here into Xojo…http://qiao.github.io/PathFinding.js/visual/ and from that page, this: view-source:http://qiao.github.io/PathFinding.js/visual/lib/pathfinding-browser.min.js

What have you tried to convert the js to Xojo?

There is an old article in XDev magazine about path finding. I don’t think they did Manhattan. See http://www.xdevmag.com/browse/1.5/

I highly recommend the book Mazes for Programmers by Jamis Buck. Link

I’ve converted a lot of the code into Xojo and would be happy to share. I have a “playground” app which lets you try various maze generation algorithms as well as pathfinding algorithms. sample video for 9 x9 grid

You should be able to adapt to your scenario. PM if interested.

Have you read the old articles on Robotics A.I. on my blog? It is old RealBasic code, but maybe it could be helpful. It covers pathfinding and even MCL (Monte Carlo Localization).

https://alwaysbusycorner.com/?s=robot

[quote=350409:@Alain Bailleul]Have you read the old articles on Robotics A.I. on my blog? It is old RealBasic code, but maybe it could be helpful. It covers pathfinding and even MCL (Monte Carlo Localization).

https://alwaysbusycorner.com/?s=robot[/quote]

Wow, that’s going to be very useful. Thanks!

@Peter Fargo - will do, thanks!

I will have to look it up… but I found (and implemented) a path routing algorithm for my “SnapDragon” (visio-clone) a few years back… I don’t recall the algorithm (A*-List???) , but it was not too difficult to make work

+1 on Alain’s blog. All his projects are fascinating to peruse :slight_smile:

So, other projects have settled down and I decided to try to tackle this again.

I’ve got a project sort of working, but sometimes wildly failing.

I think I’m not sorting my open nodes correctly.

I’m adding nodes to an array and each node has its fValue as integer and I’m trying to sort to put the lowest at the top (index 0), to then identify it and set it as current, put it in the closed list and then remove from the open list.

These are my functions:

Calling this in the FindPath method

Dim currentsquare as cls_cell = LowestF

[code]Public Function LowestF() as cls_cell
aroOpenList.sort(AddressOf fCompare)

Return aroOpenList(0)
End Function

[/code]

And

Public Function fCompare(value1 as cls_cell, value2 as cls_cell) as integer
  If value1.fValue > value2.fValue Then Return 1
  If value1.fValue < value2.fValue Then Return -1
  Return 0
End Function

Is that correct?

The project is here if anyone is interested, but it’s still in a skeleton stage.

https://mega.nz/#!AkUj2ajB!Mi4i4g29Kbi2oVpwas9VCsEs43-7TpNKc7kOl0XwJ3s

The project auto-sets the wall and target, but clicking sets a start cell. But sometimes it goes wildly off base.