Page 2 of 10
Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search
Posted: Sun May 27, 2012 7:45 pm
by bartbes
The problem is that io.read wait for input, preventing the rest of the game from running.
Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search
Posted: Sun May 27, 2012 7:47 pm
by coffee
Roland_Yonaba wrote: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.
Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search
Posted: Sun May 27, 2012 7:55 pm
by Roland_Yonaba
bartbes wrote: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.
Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search
Posted: Thu Jun 14, 2012 5:32 pm
by 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!
Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search
Posted: Thu Jun 14, 2012 5:59 pm
by vernon
if I allow diagonals, will diagonal steps cost sqrt(2) times as much as horizontal movement?
Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search
Posted: Thu Jun 14, 2012 9:16 pm
by Zeliarden
Nice! Easy to use. Here is a test with Jumper and ATL
Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search
Posted: Thu Jun 14, 2012 9:27 pm
by Nixola
vernon wrote:if I allow diagonals, will diagonal steps cost sqrt(2) times as much as horizontal movement?
In Zeliarden's demo they cost sqrt(2)
Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search
Posted: Thu Jun 14, 2012 11:02 pm
by 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.
Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search
Posted: Fri Jun 15, 2012 6:59 am
by 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.
Re: [Lib/Lua] Jumper : 2D Pathfinder with Jump Point Search
Posted: Fri Jun 15, 2012 8:42 am
by Roland_Yonaba
Zeliarden wrote: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...
vernon wrote: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).
MarekkPie wrote: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.