Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Jumper With Hexagons (Success!!!)

edited April 2015 in Questions Posts: 342

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

Comments

  • Posts: 2,020

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

  • edited April 2015 Posts: 342

    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.

  • dave1707dave1707 Mod
    Posts: 9,724

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

  • IgnatzIgnatz Mod
    Posts: 5,396

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

  • edited April 2015 Posts: 342

    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!

  • edited April 2015 Posts: 342

    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

  • dave1707dave1707 Mod
    Posts: 9,724

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

  • edited April 2015 Posts: 342

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

  • dave1707dave1707 Mod
    Posts: 9,724

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

  • Jmv38Jmv38 Mod
    Posts: 3,297

    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
    
    
  • Jmv38Jmv38 Mod
    edited April 2015 Posts: 3,297

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

  • Jmv38Jmv38 Mod
    Posts: 3,297

    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.

  • Jmv38Jmv38 Mod
    Posts: 3,297

    good job!

  • edited April 2015 Posts: 342

    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)

  • Jmv38Jmv38 Mod
    edited April 2015 Posts: 3,297

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

  • edited April 2015 Posts: 342

    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.

  • Jmv38Jmv38 Mod
    Posts: 3,297

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

  • edited April 2015 Posts: 342

    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.

  • Jmv38Jmv38 Mod
    Posts: 3,297

    example of problems, i drew an arrow to each one

  • edited April 2015 Posts: 342

    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!

  • Jmv38Jmv38 Mod
    Posts: 3,297

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

  • Eureka! And thank you!

  • dave1707dave1707 Mod
    Posts: 9,724

    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
  • Posts: 212

    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.

  • dave1707dave1707 Mod
    Posts: 9,724

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

  • edited April 2015 Posts: 212

    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.

  • dave1707dave1707 Mod
    Posts: 9,724

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

  • dave1707dave1707 Mod
    Posts: 9,724

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

  • dave1707dave1707 Mod
    Posts: 9,724

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

  • edited April 2015 Posts: 212

    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!

  • dave1707dave1707 Mod
    Posts: 9,724

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

Sign In or Register to comment.