Jumper With Hexagons (Success!!!)

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\
THETASTAR\
ASTAR\
DIJKSTRA")
    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

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

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

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.

@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.

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).

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!

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

@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.

@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)

@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.

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.

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)

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

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.

Ah, thank you very much Jmv :slight_smile: 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.

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.

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!

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

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.