Howdy, Stranger!

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

Path finder (again)

dave1707dave1707 Mod
in Code Sharing Posts: 9,808

Here’s another kind of useless program. I modified this from an earlier version I wrote. It finds the shortest path from a circle in the upper right corner to the lower left corner. There are red circle barriers that it has to go around. Tap the square to find the shortest path or no path, or tap the screen to add more barriers. Once the path is shown, tap the square to start another. Currently the size is 30, but it can be changed all the way to 1. If you’re below a size of maybe 10, depending on your device, it will be slow so you’ll have to be patient. I try to find the shortest path manually just to see if it agrees with me. Of course, once you get to a smaller size, it will be too small to try manually. At the lower sizes, it reminds me of a lightning bolt with the zig zags.

viewer.mode=FULLSCREEN

function setup()
    size=30

    fontSize(25)    
    initializeVariables()
    initializeTable()
    addBarriers()
    setStartFinish()
end

function initializeVariables()
    moveO={-1,1,0,1,1,0,0,-1,-1,-1,-1,0}  -- odd line movement
    moveE={0,1,1,1,1,0,1,-1,0,-1,-1,0}    -- even line movement
    sq=math.sqrt(3)/2
    xSize=WIDTH//size-1
    ySize=HEIGHT//size
    find,showPath=false,false
    count,pathPoints=0,0
    path,locTab={},{}
end

function initializeTable()
    -- fill table with 9999
    tab={}
    for x=1,xSize do
        tab[x]={}
        for y=1,ySize do
            tab[x][y]=9999
        end
    end
end

function addBarriers()
    -- add barriers to table, set to 9998
    for z=1,xSize*ySize/2 do
        x=math.random(xSize)
        y=math.random(ySize)
        if tab[x][y]~=9998 then
            tab[x][y]=9998
            count=count+1
        end
    end
end

function setStartFinish()    
    start=vec2(3,3)  -- starting x,y value      
    tab[start.x][start.y]=0 -- set table start to 0
    finish=vec2(xSize-2,ySize-2)  -- ending x,y value
    tab[finish.x][finish.y]=9997    -- set table finist to 9997
end

function draw()
    background(0)
    fill(255)
    rect(WIDTH-60,HEIGHT-60,60,60)
    if not showPath then
        text("Barriers  "..count,WIDTH/2,HEIGHT-35)
        text("Tap screen for more barriers or tap square to find shortest path",WIDTH/2,HEIGHT-75)
    else
        text("Tap screen for restart",WIDTH/2,HEIGHT-75)
        text("Path points  "..pathPoints,WIDTH/2,HEIGHT-35)
    end
    locTab=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 then
                fill(234, 255, 0)   -- set start and finish color
            elseif locTab[x][y]==9996 then
                fill(255)           -- set path color
            elseif locTab[x][y]==9998 then
                fill(255,0,0)       -- set barrier color
            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
    findPaths()
    showPaths()
end

function findPaths()  
    if find then
        findAllPaths()  -- returns a table of the path
        findShortestPath()
        find=false
        showPath=true
    end  
end

function showPaths()
    if showPath then -- show path
        if pathPoints==0 then
            fill(255)
            text("NO PATH FOUND",WIDTH/2,HEIGHT/2)
        else
            for zz=1,#path do
                locTab[path[zz].x][path[zz].y]=9996
            end
        end
    end
end

function touched(t)
    if t.state==BEGAN then
        if not showPath then
            if t.x>WIDTH-60 and t.y>HEIGHT-60 then  -- find path
                find=true
                setStartFinish()
            else
                for z=1,100 do  -- add 100 extra barriers
                    x=math.random(xSize)
                    y=math.random(ySize)
                    if tab[x][y]~=9998 then
                        tab[x][y]=9998
                        count=count+1
                    end
                    setStartFinish()
                end
            end
        else
            viewer.restart()    -- restart
            return
        end
    end
end

function findAllPaths()    
    local v,c,val,x,y=0,0,0,0,0

    -- calculate all the path distances from start to finish
    local locTab1={vec2(start.x,start.y)}
    while find do
        local locTab2={}
        for s=1,#locTab1 do
            for z=1,12,2 do
                if locTab1[s].y%2==0 then
                    mx=moveE[z]
                    my=moveE[z+1]
                else
                    mx=moveO[z]
                    my=moveO[z+1]
                end
                x=locTab1[s].x
                y=locTab1[s].y 
                if x+mx>=1 and x+mx<=xSize and y+my>=1 and y+my<=ySize then
                    if locTab[x+mx][y+my]==9999 then
                        val=locTab[x][y]
                        if val+1<locTab[x+mx][y+my] then
                            locTab[x+mx][y+my]=val+1
                            table.insert(locTab2,vec2(x+mx,y+my))
                        end
                    elseif locTab[x+mx][y+my]==9997 then
                        find=false
                    end
                end  
            end
        end
        locTab1=locTab2
        if #locTab2==0 then
            find=false
            return
        end
    end
end

function findShortestPath()
    -- find the shortest path distance from finish to start
    local ex1,ey1=finish.x,finish.y
    local xh,yh=ex1,ey1
    local c=0
    local find=true
    while find do
        val=locTab[ex1][ey1]
        -- move through moveO or moveE table by 2
        for z=1,12,2 do
            if ey1%2==0 then
                x=ex1+moveE[z]
                y=ey1+moveE[z+1]
            else
                x=ex1+moveO[z]
                y=ey1+moveO[z+1]
            end
            if x>=1 and x<=xSize and y>=1 and y<=ySize then
                v=locTab[x][y]
                if v<val then
                    val=v
                    xh=x
                    yh=y
                end
            end                      
        end
        ex1=xh
        ey1=yh
        -- reached the start points
        if xh==start.x and yh==start.y then
            pathPoints=#path
            return
        else
            table.insert(path,1,vec2(xh,yh))
        end
        c=c+1
        if c>2000 then   -- prevent infinate while loop
            find=false    
        end
    end 
end

Comments

  • Posts: 18

    Is it a random method? I got rather satisfied with I think it is called the breath first search method and keep using that one. I have a a* one that I can port if needed.

    I did program a brute force pathfinder once. But this one gets slower with each additional step. That version just creates every possible path starting at one step and going up.

  • dave1707dave1707 Mod
    Posts: 9,808

    @Pakz This code finds every path from the start to the finish position. It also keeps track of how many steps it has to take for the paths. It then determines which of the 6 paths around the finish has the least amount of steps and follows that path back to the start. So it always finds the shortest path or one of them if several paths are equal. I have no use for this code other than it gave me a problem to solve and code to write.

  • Posts: 1,303

    Here's one I did. Tap once to choose starting pos, once to choose ending pos. Additional taps add obstacles where you tap.

    Cell = class()
    Cell.indices = { {-1,1}, {0,1}, {1,1}, {-1,0}, {1,0}, {-1,-1}, {0,-1}, {1, -1}}
    Cell.indices = { {0,1}, {-1,0}, {1,0}, {0,-1} }
    
    function Cell:init(x,y,value)
        self.x = x
        self.y = y
        self.target = false
        self.obstacle = false
        self.path = false
        self.start = false
        self.distance = MaxDistance
        self.plaincolor = color(0,0,0)
        self.highlighted = false
    end
    
    function Cell:draw(grid)
        local step = grid.step
        dx = self.x * step
        dy = self.y * step
        pushStyle()
        strokeWidth(2)
        stroke(255,255,255)
        fill(self:color())
        rect(dx,dy, step,step)
        fill(255)
        if self.highlighted then fill(0) end
        text(self.distance, dx+step/2, dy+step/2)
        popStyle()
    end
    
    function Cell:touched(grid, touch)
        if touch.state == BEGAN then
            local step = grid.step
            lowx = self.x*step
            lowy = self.y*step
            if ( touch.x > lowx and touch.y > lowy and touch.x < lowx + step and touch.y < lowy+step) then
                self:changeState()
            end
        end
    end
    
    -----
    
    function Cell:changeState()
        if State == "start" then Grid.start = self; self.start = true; State = "target"; return end
        if State == "target" then Grid.target = self; self.target = true; State = "obstacle" return end
        self.obstacle = not self.obstacle
    end
    
    function Cell:color()
        if self.start then return color(0,0,255) end
        if self.target then return color(0,255,0) end
        if self.obstacle then return color(255,0,0) end
        return self.plaincolor
    end
    
    function Cell:distanceFrom(c)
        if true then return 1 end
        local t = math.abs(c.x - self.x) + math.abs(c.y - self.y)
        if t == 1 then return 10 else return 14 end
    end
    
    function Cell:highlight()
        if self.highlighted or self.target or self.obstacle then return end
        self.highlighted = true
        self.plaincolor = color(255,255,0)
        Grid.highlightQueue:pushRight(self)
    end
    
    function Cell:highlightNeighbors()
        function compare(c1,c2)
            return Grid.target:vecDist(c1) < Grid.target:vecDist(c2)
        end
        if not self.distance then return end
        if self.obstacle then return end
        local ok = {}
        for i,c in ipairs(self:neighbors()) do
            if c.distance < self.distance then
                if self.distance == 2 then
                    print("inserting", self.x, self.y, self.distance, c.x, c.y, c.distance)
                end
                table.insert(ok, c)
            end
        end
        table.sort(ok,compare)
        local bestDistance = Grid.target:vecDist(ok[1])
        for i,c in ipairs(ok) do
            if  Grid.target:vecDist(c) == bestDistance then
                c:highlight()
            end
        end
    end
    
    function Cell:highlightPath()
        Grid:processHighlight(self)
    end
    
    function Cell:neighbors()
        local cells = {}
        for i, p in ipairs(Cell.indices) do
            local cell = Grid:at(self.x + p[1], self.y + p[2])
            table.insert(cells, cell)
        end
        return cells
    end
    
    function Cell:setDistance(dist)
        if self.obstacle then return end
        if self.distance > dist then
            self.distance = dist
            Grid.pathQueue:pushRight(self)
        end
    end
    
    function Cell:setNeighbors()
        if self.obstacle then return end
        for i,c in ipairs(self:neighbors()) do
            c:setDistance(self.distance + self:distanceFrom(c))
        end
    end
    
    function Cell:setTarget()
        self.target = true
        self.distance = 0
        print("i am target", self.x, self.y)
    end
    
    function Cell:showPath()
        self.distance = 0
        Grid:processPath(self)
    end
    
    function Cell:vecDist(c)
        local s1 = vec2(self.x, self.y)
        local c1 = vec2(c.x,c.y)
        return s1:dist(c1)
    end
    
Sign In or Register to comment.