Path finder (again)

Code Sharing
1

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
2

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.

3

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

4

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