Jumper : 2D Pathfinder with Jump Point Search (v.1.8.1)

[bartbes]

The problem is that io.read wait for input, preventing the rest of the game from running.

[coffee]

Right... It was easy to write... But not sure to work on every platform..
I 'll have to rewrite that demo, avoiding IO for input..
Thanks for taking time to look into it, I strongly appreciate.
Would you mind create an issue for this ?

You could consult first Robin or bartbes about the issue without do first any changes. They could have an easy solution for you. I wouldn't mind add but I don't have a git account.

EDITED: As I see bartbes already answered meanwhile. Thanks for help.

[Roland_Yonaba]

The problem is that io.read wait for input, preventing the rest of the game from running.

Thanks for confirming.
I'll definitely work on an alternative...This night or tomorrow.

EDIT : Well, as I got some spare time this morning, I've been able to work on this.
I think I got fixed the issue that was occuring when diagonal moves were disabled. I had to come back on the way jump point search was implemented, tracing how the algorithm was working, and adding some tweaks to handle straight moves cases.
It seems to be working fine now. Hopefully, I'll be releasing this afternoon, i got a bunch of tests to perform first.
I also implemented a path smoother function, and had it working sucessfully.
Screenies coming.

[Roland_Yonaba]

Okay, time to bump this, since I have made some significant changes and progresses.
See the first post updated.
There should no longer be problems with Mac OSX users with the benchmark demo.
Comments and useful advises will be appreciated, thanks!

[vernon]

if I allow diagonals, will diagonal steps cost sqrt(2) times as much as horizontal movement?

[Zeliarden]

Nice! Easy to use. Here is a test with Jumper and ATL

[Nixola]

if I allow diagonals, will diagonal steps cost sqrt(2) times as much as horizontal movement?

In Zeliarden's demo they cost sqrt(2)

[MarekkPie]

To make things easier, you could change orthogonal movement to 10 and diagonal movement to 14, since sqrt(2) is about 1.4. That will keep things similar, without having to call sqrt(2) constantly.

However, in reality, that kind of cost is arbitrary. It just represents what you want the cost to be. Think about strategy games like Civilization. Often, there is a movement penalty for crossing a river or moving through a forest. That movement penalty is essentially just an inflation in the cost to move over those particular tiles.

I haven't looked at Roland's implementation, but the ideal is to not hard-code in that movement information, so the user can change things around, like the above example, as they please.

[Robin]

Also, assuming there are no different costs associated to each tile, then as long as the cost for going diagonally is < 2 and > 1, it will do the thing you expect.

At > 2, it is cheaper not to cut corners, so you only get straight lines, and at < 1 going in straight lines is more expensive than zig-zagging.

[Roland_Yonaba]

Nice! Easy to use. Here is a test with Jumper and ATL

Thanks, I loved your demo.
By the way, you create a Canvas that you did not use.

Code: Select all

-- line34
canvas = love.graphics.newCanvas( winw, winh )

Hopefully, cause my graphic card doesn't support Canvas...

if I allow diagonals, will diagonal steps cost sqrt(2) times as much as horizontal movement?

Yes. A diagonal move cost is calculated using Euclidian heuristic internally.

Code: Select all

local function EUCLIDIAN(dx,dy) return math.sqrt(dx*dx+dy*dy) end

-- G cost is calculated from a jump point to the node expanded using Euclidian distance heuristic
			if not jumpNode.closed then
			dist = EUCLIDIAN(jx-x,jy-y)
			ng = node.g + dist
				if not jumpNode.opened or ng < jumpNode.g then
				jumpNode.g = ng
				jumpNode.h = jumpNode.h or (heuristic(jx-endX,jy-endY))
				jumpNode.f = jumpNode.g+jumpNode.h
				jumpNode.parent = node
					if not jumpNode.opened then
						openList:insert(jumpNode)
						jumpNode.opened = true
					else
						openList:heap()
					end
				end
			end

So, a diagonal move of (dx,dy) will cost sqrt(dx*dx+dy*dy).

I haven't looked at Roland's implementation, but the ideal is to not hard-code in that movement information, so the user can change things around, like the above example, as they please.

I am waiting for your code review, then. But what you said sounds very interesting, I'll look into it right now.