Jumper With Hexagons (Success!!!)

Monkeyman32123

I have made jumper work with Hexagons, the main code is below and there is a link to the modified Jumper library below that (I have not yet cleaned it, so while JPS and DFS are still in there, keep in mind they dont work properly).

Main:

displayMode(FULLSCREEN_NO_BUTTONS)
supportedOrientations(LANDSCAPE_ANY)
function setup()
    mapsize = 30
    map = {}
    for i=1,mapsize do
        map[i] = {}
        for j=1,mapsize do
            map[i][j] = 0
        end
    end
    for i = 1,(mapsize^2)/2.0 do
        x,y = math.random(mapsize),math.random(mapsize)
        map[y][x] = 5
    end
    start = vec2(math.random(mapsize),math.random(mapsize))
    while map[start.y][start.x] == 5 do
        start = vec2(math.random(mapsize),math.random(mapsize))
    end
    map[start.y][start.x] = 2.5
    r = (math.min(WIDTH,HEIGHT)/(math.sqrt(3)*(mapsize-1)+2))
    mpos = {}
    for i=1,#map do
        mpos[i] = {}
        for j=1,#map[1] do
            mpos[i][j] = vec2(r*((j*2)-1)+((i-1)%2)*r,r+(i-1)*math.sqrt(3)*r)
        end
    end
    print("Hello World!")
    grid = Jumper.Grid(map)
    myFinder = Jumper.Pathfinder(grid, 'DIJKSTRA', 0)
    h= function() return 0 end
    myFinder:setHeuristic(h)
    parameter.text("FINDER","DIJKSTRA",function(t) myFinder:setFinder(t) end)
    parameter.text("Allowed Finders","BFS\nTHETASTAR\nASTAR\nDIJKSTRA")
    img = image(WIDTH,HEIGHT)
    setContext(img)
    fill(255)
    fontSize(r/1.75)
    noStroke()
    for i=1,#map do
        for j=1,#map[1] do
            fill(255-map[i][j]*255/5)
            ellipse(mpos[i][j].x,mpos[i][j].y,r*2+1)
            fill(0)
            text(j..":"..i,mpos[i][j].x,mpos[i][j].y)
        end
    end
    setContext()
    spriteMode(CORNER)
end
function draw()
    background(0)
    sprite(img,0,0)
    stroke(255,0,0)
    strokeWidth(math.max(1,r/3))
    if points then for c,val in pairs(points) do
            if c>1 then
                line(mpos[val.y][val.x].x,mpos[val.y][val.x].y,mpos[points[c-1].y][points[c-1].x].x,mpos[points[c-1].y][points[c-1].x].y)
            end
    end end
end

function touched(t)
    if t.state == BEGAN then
        for i=1,#map do
            for j=1,#map[1] do
                if vec2(t.x,t.y):dist(mpos[i][j]) < r then
                    pa = myFinder:getPath(start.x,start.y,j,i)
                    if pa then
                        points = {}
                        if pa:getLength()>0 then pa:fill() end
                        for node, count in pa:nodes() do
                            points[count] = vec2(node:getX(),node:getY())
                        end
                        output.clear()
                        print(('Path length: %.2f'):format(pa:getLength()))
                    end
                end
            end
        end
    end
end

Jumper link:
https://gist.github.com/monkeyman32123/0e1b8a7543a894c2d84b

yojimbo2000

Where's the rest of the code (The Jumper data and pathfinder functions)?

Monkeyman32123

Oh, yes, i should mention that Jumper is a library downloadable from this link:
https://gist.github.com/brookesi/6593116

Monkeyman32123

I discovered that the custom heuristic i made actually WAS doing something (hooray), and the something it was doing was completely and utterly wrong (boo). Thus, I call upon the gods of problem solving that are @dave1707 and @Ignatz, please help me through this dark time. Perhaps I just dont understand how to make the heuristic at all. Or perhaps ive made a very dumb and simple mistake, who knows? But this issue is the Bane of Progress.

dave1707

@Monkeyman32123 I'm on the latest beta version of Codea and when I load the gist version of code that's needed to run your version I get errors. I'm not going to try and debug that code in order to debug your code. So you're on your own unless someone else wants to help.

Ignatz

Too much code for me.

The key to debugging is isolating where the problem is. I do that using print statements, by commenting out as much of the program as possible, and similar methods (including a lot of patience).

Monkeyman32123

Odd, im not getting any errors running that version of the code, so it must be something with the beta, sorry about that . On my version the only issue is with the heuristic function I developed. And it isnt causing error reports so I cant track it that way. But I completely understand not wanting to debug the entire Jumper library, thats every coder's nightmare. Must be a bigger gap between 2.3 and the beta than i thought! But thank you anyways for your swift responses, they are always greatly appreciated!

Monkeyman32123

I apologize for this @dave1707 and @Ignatz, but it seems I gave the wrong additional link for jumper. There are two and the one I gave was Ignatz's stress test for Jumper instead of Brookesi's port. Sorry about that, hopefully the code in this link works a little better:

https://gist.github.com/brookesi/6593116

dave1707

@Monkeyman32123 That version works better. I added your code to it and ran it. I'm not sure what it's supposed to do, but if I tap on one of the circles, it gives me a path length.

Monkeyman32123

@dave1707 it gives a proper path if the circles were arranged rectangularly rather than hexagonally. The path travels to circles that arent adjacent. I need the path to only go to adjacent circles. That means on the left-shifted rows not allowing them to travel diagonally right, and on the right shifted rows not going diagonally left. I thought id be able to achieve this with a custom heuristic, but i cant seem to restrict moves to adjacent circles with the heuristic. My initial thoughts are either that i dont understand how the heuristics work at all (and i surely cant digest the Jumper class code), or that there is a bug in the Jumper code (in which case, this discussion is pretty well moot unless someone wants to dig through that)

dave1707

@Monkeyman32123 I don't know anything about the jumper code, but if it's made to work with squares, trying to make it work with hexagons isn't going to work.

Monkeyman32123

Well, the code is designed to pathfind diagonally as well as orthagonally, so making it work with hexagons is just a matter of omitting two directions as possible moves depending on the y-value of the current node.

Monkeyman32123

That doesnt mean its possible, but it doesnt rule it out as a possibility either. That's why i thought to look into the custom heuristic aspect, because i believe this kind of thing is exactly what they are for. I was hoping Ignatz could help here as he ported it and wrote the benchmark. All i really need is some greater insights into how heuristics work, but none of the jumper documentation seems to be very in-depth. I really hope you are wrong about translating its function to hexagons (especially since my hexagon map is just a tweaked rectangular map)

Jmv38

i gave it a try, here is my code

-- TD

-- Use this function to perform your initial setup
function setup()
    map=
    {
    {0,0,0,0,0,0},
    {0,0,0,0,0,0},
    {0,0,1,0,0,0},
    {0,0,1,0,0,0},
    {0,0,1,0,0,0},
    {0,0,0,0,0,0},
    }
    r = math.floor(WIDTH/(#map*2+1))
    mpos = {}
    for i=1,#map do
        mpos[i] = {}
        for j=1,#map[1] do
            mpos[i][j] = vec2(r*((j*2)-1)+((i-1)%2)*r,r+(i-1)*math.sqrt(3)*r)
        end
    end
    print("tap a circle to make path. Longpress (>1s) to toggle it as an obstacle")
    grid = Jumper.Grid(map)
    myFinder = Jumper.Pathfinder(grid, 'ASTAR', 0)
    h = function(na,nb)
        local xa,ya = na:getX(), na:getY()
        local xb,yb = nb:getX(), nb:getY()
        local dxa = ((xa-1) % 2) * 0.5
        local dxb = ((xb-1) % 2) * 0.5

        -- the following points are rejected
        --      yyn
        --      yay
        --      yyn
        local distance = vec2((xb+dxb-xa-dxa),(yb-ya)):len()
        if (xb == xa + 1 and yb == ya + 1)
        or (xb == xa + 1 and yb == ya - 1)
--        or (xb == xa - 1 and yb == ya - 1)
--        or (xb == xa - 1 and yb == ya + 1)
        then
            distance = 100
        end
        print(string.format("%d:%d > %d:%d = %f",xa,ya,xb,yb,distance))
        return distance
    end

    myFinder:setHeuristic(h)
    --path = myFinder:getPath(2,1,mazesize*2,mazesize*2+1)

end

-- This function gets called once every frame
function draw()
    background(0)
    fill(255)
    noStroke()
    for i=1,#map do
        for j=1,#map[1] do
            if map[i][j] == 0 then
                fill(255)
            elseif map[i][j] == 1 then
                fill(127, 127, 127, 255)
            end
            ellipse(mpos[i][j].x,mpos[i][j].y,r*2)
            fill(0)
            text(j..":"..i,mpos[i][j].x,mpos[i][j].y)
        end
    end
    stroke(255, 0, 0, 255)
    strokeWidth(5)
    if points~=nil then
        local pos0 = points[1]
        for k,pos1 in pairs(points) do
            line(pos0.x, pos0.y, pos1.x, pos1.y)
            pos0 = pos1
        end
    end
end

function getPath(i,j)
    local pa = myFinder:getPath(1,1,j,i)
    if pa == nil then return end
    points = {}
    for node, count in pa:nodes() do
        print(('%d. Node(%d,%d)'):format(count, node:getX(), node:getY()))
        local j,i = node:getX(), node:getY()
        table.insert(points,{x=mpos[i][j].x, y=mpos[i][j].y})
    end
    print(('Path length: %.2f'):format(pa:getLength()))
    return pa
end

function toggle(i,j)
    if map[i][j] == 0 then      map[i][j] = 1
    elseif map[i][j] == 1 then  map[i][j] = 0
    end
end

function touched(t)
    if true then
        for i=1,#map do
            for j=1,#map[1] do
                if vec2(t.x,t.y):dist(mpos[i][j]) < r then
                    if t.state == BEGAN then
                        tstart = ElapsedTime
                    elseif t.state == ENDED then
                        dt = ElapsedTime - tstart
                        if dt < 0.5 then
                        pa = getPath(i,j)
                        else
                        toggle(i,j)
                        end
                    end
                end
            end
        end
    end
end

Jmv38

unforunately it doesnt work either, but i understand why.

1/ the heuristics is not using the distance between 2 neighbour points but between the end point and any point: this is why forcing the diagonal move to a big value doesnt forbid the diagonal path. Check the printed data to see this.

2/ the rule to forbid some diagonal moves can be modified in the jumper code itself, however i've looked at where diagonal pixels are accessed, and they are at a lot of places, without using some function like give_me_the_allowed_neighbours(node), so that means changes have to be made at many places.

Not an immediate solution then.

PS: a general advice for you: check the changes i made to your code, there are several improvements i would recommend you.
you were printing in each draw => do it once in touch only.
keep the code in some small function, then call them in touched.
add some functions to visualize the results: path tracing, print the intermediate results of heuristics, etc... this helps to undestand a lot of faster what is going on.

Monkeyman32123

Ah, thank you very much Jmv I understand now, and I cant thank you enough for taking so much time to figure this out. I will take the changes to heart (already have!) as well. I was sure it would work because in Yonaba's dev blog he mentioned that he added compatibility for semi-walkability that only allowed going to a point from certain points. I was certain this feature was implemented in the heuristic, but it is good to know that I am dead wrong . Perhaps I will continue my hunt for this gem of a feature, or perhaps it really doesn't exist. Either way, I want to thank you again for your help, time, and making me understand.

Jmv38

you are welcome!
Dont give up porting into hexagons though: there are several places where diagonal pixels are checked explicitly, but maybe less than 10, so it may not be too difficult to change this. If you do so, try to use an 'allowed_neighbours()' function everywhere, debug will be much easier.

Monkeyman32123

Thank you muchly! I will (attempt) to understand the Jumper class to port it. I dont understand the binary heap parts at all and its hard to visualize the structure of it all as it bounces around a lot, but im going to look into porting it to hexagons. If i succeed I think I'll probably post a lite version of jumper stripped down to the two search methods that work fastest and most accurately with the hexagonal modifications. Thanks again for your help and for giving me hope in the possibility of a hexaport. Off to the drawing board!

Monkeyman32123

Update: I have succeeded in porting Jumper to Hexagons. So far it only works with the Dikjstra search method, but I hope to soon expand to the others. JPS, the fastest method, unfortunately doesnt cooperate with my fix, so I'll have to devise a completely new fix just for it. If I can't get the fixes to work with the other search algorithms I will cut them entirely before releasing the codes

Monkeyman32123

Update 2: Ive made jumper work perfectly with Hexagons using all but two of the search methods. JPS and DFS. JPS does not work at all, whereas DFS TECHNICALLY works but gives some of the longest paths possible to go simple two-tile distances, rather silly.

Jmv38

good job!

Monkeyman32123

Thank you! After studying the code a lot more, I devised an even more simple solution that involves the changing of only two lines of code. On line 430 in the function Grid:GetNeighbors(), where it checks diagonal neighbors replace:

if n and self:isWalkableAt(n._x, n._y, walkable, clearance) then

With

if n and self:isWalkableAt(n._x, n._y, walkable, clearance) and 
not ((node._y%2)*2-1==diagonalOffsets[i].x) then

And then on line 1224 in the pathfinder function replace:

newPathfinder:setTunnelling(false)

With

newPathfinder:setTunnelling(true)

And then VOILA! It works with all search methods except JPS (and DFS gives awful paths but works)

Jmv38

I've made the changes you said above, but there are still problems on my version of the project.
What is your heuristics?

Monkeyman32123

Ope! My apologies, I set it to the default 'MANHATTAN' heuristic.

EDIT: all of the non-jumper code is in the initial post now

EDIT EDIT: All of the stuff is in the original post

EDIT EDIT EDIT: As soon as I remove JPS I will upload a link to the Hexagonal Ported code so you dont have to manually replace lines.

Jmv38

with your code touch 24:21 => not the shortest path? And what about tunnelling through the walls?

Monkeyman32123

I havent had tunneling issues, are you having issues with the tunneling? If so, please do tell. and I'm still working out how to get it to give the shortest path, still some odd things going on in that department (that said, DIJKSTRA seems to give the shortest path more often than not)

Due to the Hexagons tunneling diagonally is exactly what we want, otherwise it cant properly find a path. I have an illustration of it as it took me a while to understand so i had to draw it out

EDIT: ah, I see it now, the manhattan heuristic is inaccurate because of the new arrangement. It works well enough, but I set the heuristic to:

function() return 0 end

and it seemed to work out a bit nicer. Makes the cost the same to go to any neighbouring hexagon, as they are all the same distance.

Jmv38

example of problems, i drew an arrow to each one

Monkeyman32123

Ah yes, that's precisely what I was afraid of. There are two lines in the Grid:getNeighbors() function that are identical, except in different parts. You replaced the adjacent move case instead of the diagonal one (My fault, shoudlve had it in a gist straight out). Sorry for all that. I have the correct main and the modified Jumper code in the original post. Thanks for sticking with me through all of this @Jmv38, it's greatly appreciated NOW we should get some good lines going!

Jmv38

you are right, now it seems to work perfectly.
Great job!

Monkeyman32123

Eureka! And thank you!

dave1707

This discussion got me interested in a pathfinder routine. @Monkeyman32123 wanted to use hexagon directions, but the Jumper code he wanted to use didn't work and he needed to fix it. I looked at the Jumper code, actually the last line, and saw that it was over 1400 lines. No way was I going to use that, so I decided to see if I could write my own. So here is my attempt at pathfinding using hexagon directions. The majority of the code is just setting the barriers and displaying the results. Once the program is started, you'll see a GREEN starting point ( lower left) and a GREEN ending point ( upper right ). To create RED barriers, slide your finger around the screen. Create as many barriers as you want. Once those are created, tap the BLUE circle in the upper right to calculate the path. There will be a fast path in GREEN, and a slower YELLOW path will follow the GREEN one. If a path isn't found, a message will show on the screen. I don't have a use for this, it was mainly to see if I could write the code and to understand how pathfinding worked.

displayMode(FULLSCREEN)
supportedOrientations(LANDSCAPE_ANY)

function setup()
    size=35
    sq=math.sqrt(3)/2
    xSize=28
    ySize=24
    tab={}
    for x=1,xSize do
        tab[x]={}
        for y=1,ySize do
            tab[x][y]=9000
        end
    end
    start=vec2(5,5)  -- starting x,y values
    tab[start.x][start.y]=0
    finish=vec2(24,20)  -- ending x,y values
    tab[finish.x][finish.y]=9001
end

function draw()
    background(40, 40, 50)
    fill(255)
    local tab1=tab
    for x=1,xSize do
        for y=1,ySize do
            fill(154, 213, 223, 163)
            if x==start.x and y==start.y or 
                    x==finish.x and y==finish.y or tab1[x][y]==700 then
                fill(0,255,0)
            elseif tab1[x][y]==9998 then
                fill(255,0,0)
            elseif x==xSize and y==ySize then
                fill(0,0,255)   -- blue circle for start of path search
            elseif tab[x][y]==8888 then
                fill(255,255,0)
            end
            if y%2==0 then
                ellipse(x*size+size/2,y*size*sq,size+2)
            else
                ellipse(x*size,y*size*sq,size+2)
            end
        end
    end  
    if find then
        path=calcPath(tab)  -- returns a table of the path
        find=false
        showPath=1
    end  
    if showPath==1 then -- show fast path in green
        if path==nil then
            fill(255)
            fontSize(30)
            text("NO PATH FOUND",WIDTH/2,HEIGHT/2)
        else
            for zz=1,#path do
                tab[path[zz].x][path[zz].y]=700
            end
            zz=1
            zy=0
            showPath=2
        end
    elseif showPath==2 and zz<=#path then   -- show slow path in yellow
        tab[path[zz].x][path[zz].y]=8888
        zy=zy+1
        if zy>10 then
            zz=zz+1
            zy=0
        end
    end
end

function touched(t)
    if t.state==BEGAN and showPath==nil then
        if t.x>WIDTH-50 and t.y>HEIGHT-50 then
            find=true
        end
    end
    if t.state==MOVING then
        x=math.floor(t.x/size)
        y=math.floor(t.y/size/sq)
        if x>=1 and x<=xSize and y>=1 and y<=ySize then
            tab[x][y]=9998
        end
    end
end

function calcPath(tab1)
    local moveO={-1,1,0,1,1,0,0,-1,-1,-1,-1,0}
    local moveE={0,1,1,1,1,0,1,-1,0,-1,-1,0}
    local x2,y2,v,c,val,path=0,0,0,0,0,{}
    -- calculate all the path distances
    while find do
        for x=1,xSize do
            for y=1,ySize do
                if tab1[x][y]<9000 then
                    val=tab1[x][y]
                    for z=1,12,2 do
                        if y%2==0 then
                            x2=x+moveE[z]
                            y2=y+moveE[z+1]
                        else
                            x2=x+moveO[z]
                            y2=y+moveO[z+1]
                        end
                        if x2>=1 and x2<=xSize and y2>=1 and y2<=ySize then
                            v=tab1[x2][y2]
                            if v<9001 then
                                if val+1<v then
                                    tab1[x2][y2]=val+1
                                end
                            elseif v==9001 then
                                find=false
                            end
                        end 
                    end
                end
            end
        end
        c=c+1
        if c>300 then   -- upper limit of the while loop
            find=false
            return
        end
    end
    -- find the shortest path distance
    local ex1=finish.x
    local ey1=finish.y
    c=0
    find=true
    while find do
        val=tab1[ex1][ey1]
        for z=1,12,2 do
            if ey1%2==0 then
                x2=ex1+moveE[z]
                y2=ey1+moveE[z+1]
            else
                x2=ex1+moveO[z]
                y2=ey1+moveO[z+1]
            end
            if x2>=1 and x2<=xSize and y2>=1 and y2<=ySize then
                v=tab1[x2][y2]
                if v<val then
                    val=v
                    xh=x2
                    yh=y2
                end
            end                      
        end
        ex1=xh
        ey1=yh
        if xh==start.x and yh==start.y then
            return path
        else
            table.insert(path,1,vec2(xh,yh))
        end
        c=c+1
        if c>300 then   -- upper limit of the while loop
            find=false    
        end
    end    
end

matkatmusic

Well, @dave1707 that really crashed the shit out of my ipad lol. try drawing a red-circle loop around one of the green circles and see what happens.

dave1707

@matkatmusic I tried that ( 6 RED circles surrounding a GREEN one ) and I get the message "NO PATH FOUND". I then tried RED circles surrounding each of the GREEN circles and I get the same message. No matter how I create the barriers or how many RED circles I create around the GREEN one, I either get a path created or the message "NO PATH FOUND".

matkatmusic

right. it displays that, and then it froze my ipad. power button didn't work, home button didn't work. had to hold down home+power for a while to restart it. are you on the beta team? i'm not, so that might be why you haven't experienced the crash.

dave1707

@ matkatmusic Do you get a path created if you don't create any RED barriers. Do you get a path if you create a simple RED barrier. Do you crash only if there isn't a path.

dave1707

@matkatmusic I tried loading the program on my iPad 1 and didn't have any problems. I got NO PATH FOUND or a path was created.

dave1707

@matkatmusic Does it freeze every time you try it, or did you only try it once. I'm running the latest beta on my iPad Air, but my iPad 1 has the old version of Codea and the code ran OK.

matkatmusic

it seemed to freeze when I hit the reload or back buttons in the corner. i tried it again a few times. pretty neat program you wrote when it works!

dave1707

@matkatmusic Havn't had any problems with the reload or back buttons either. I even tried it a lot of times on the iPad 1with no problems.