horomanJumpSearch

[horoman]

The goal is to implement an algorithm, that solves a shortest path problem on a two dimensional discrete map
where each node belongs to a category and has some straight and diagonal crossing costs assigned which are grater or equal the Euclidean distance. The categories are prioritized and the algorithm does not care about the costs of a category as long as the costs of the higher priority categories are minimized.

The algorithm is thought to be used on grid maps with areas of nodes of the same category and costs.
It will be built on the so called Jump Point Search which itself has it seeds in the label correcting algorithm, in particular on the A*-algorithm.

Here I would like to make a list, what needs to be done until the algorithm works. So this first entry will change over time.

• (done) Implement new heap
• (done) Implement new Node handling
• (done) exchange forced Neighbour check
• (done) Implement new cost calculation
• (done) Implement new findNeighbours
• verify and test

[horoman]

I made some inital thoughts about the horomanJumpSearch algorithm:


Out of this I'll try do define what's to do...

[horoman]

The code from Yonaba just expects a grid table with binary content.
It then builds a grid object with functions and with nodes. These nodes basically just have a x and y value (and a compare function).
For the new algorithm one has to provide more than only binary content. This is not possible within the actual code. I think it is easier to make a new framework, than adapt the current to fit the needs. Adapting would basically result in that I need to consider about all the other algorithms and functionalities as well, which makes it more complex. This is not necessary as we don't need these other functions. If we do once in the future we can either integrate them in the new framework or just integrate the current framework to be use side by side with the new one.

Therefore I will start with a new framework, but of course do a lot of glimpsing of and copy paste from the old one...

[Edit]
I will check that again, I have just had an idea how I could maybe easily adapt the "old" framework from Yonaba...

[horoman]

If we do it with the 'old' framework you loop through the map twice: First you create your grid, then you put it into the framework and the framework will loop through it again, to find the map's boundaries. This is not necessary. I'll write a new one, then I can do what pleasures me ;-).

[Edit]
I am still struggling, it would be a lot of work (or a lot of copy paste)...

[horoman]

Well, I started in a new file, but copy/pasted the Pathfinder framework.
With the Grid class I started from scratch
Within the other classes I used some functions, some I implemented newly, some I left away.

And: finally a first test on an empty filed worked. Strike! ;-). Hope it will work on other fields, espesially on ones with grain, too....

[JakobTischler]

Sorry I haven't actively participated here yet, but my mind isn't ready yet for that whole complex thing. Especially writing new algorithms from scratch :)

[horoman]

No problem. It's not that complex. Maybe we skype once. Ask, explain and discuss will be easier then.

[horoman]

After some bug fixing the code now passed a first test. There may be unnecessary steps and allowDiagonal=false will not work (havn't thought about it yet), but it worked.
Have a look at it when you have time (who ever reads this;-) ) and report.
To use it, replace self.testCourse and self.hjsRoute in cppf.lua. Note that self.hjsRoute uses coordinates of the map and not the grid indices.
I am talking about the horomanJumpSearch branch by the way.

[horoman]

[horoman]

allowDiagonal = false