-
-
Save MacroMachines/8c4f2ee4b6d135950fa804fa1cf6321e to your computer and use it in GitHub Desktop.
Pathfinding on an 'infinite' isometric grid.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| --# Main | |
| function setup() | |
| displayMode(FULLSCREEN) | |
| Grid.init(64,32) | |
| touches = 0 -- Number of touches | |
| vx = 0; vy = 0 -- View position | |
| -- Create some tiles using the class | |
| goal = Tile(-10, 0, 'yellow') | |
| start = Tile(0, 0, 'green') | |
| local walls = {{1,2},{0,2},{-1,2},{-2,2},{-2,1},{-2,0},{-2,-1},{-2,-2},{-3,-2},{-4,0},{-5,0},{-6,0},{-5,-1},{-5,-2},{-5,-3},{-5,-4},{-5,-5},{-4,-6},{-5,-6},{-6,-6}} | |
| for i,v in ipairs(walls) do Tile(v[1], v[2], 'blue', true) end | |
| end | |
| function touched(touch) | |
| -- Touch counter | |
| if touch.state==BEGAN then touches = touches + 1 end | |
| if touch.state==ENDED then touches = math.max(touches - 1,0) end | |
| -- Move the view with two fingers | |
| if touches==2 then | |
| vx = vx + touch.deltaX/2 | |
| vy = vy + touch.deltaY/2 | |
| end | |
| -- Retrieves touched tile | |
| if touches==1 then | |
| goal.p, goal.q = getpq(touch.x-vx, touch.y-vy) | |
| end | |
| end | |
| function draw() | |
| translate(vx, vy) | |
| background(255) | |
| if (goal.p~=pp or goal.q~=qq) then | |
| path = findPath(0, 0, goal.p, goal.q) | |
| end | |
| -- Draw tile instances and path | |
| for i,v in ipairs(tiles) do v:draw() end | |
| fill(127, 127, 127, 50) | |
| for i,v in ipairs(path) do drawTile(v.p, v.q) end | |
| -- Draws grid | |
| Grid.draw() | |
| -- Shows the tile coordinates of the selection | |
| fill(0) | |
| fontSize(32) | |
| text(goal.p..", "..goal.q, WIDTH/2-vx, HEIGHT-50-vy) | |
| -- Sets the previous selection coordinates | |
| pp = goal.p | |
| qq = goal.q | |
| end | |
| --# Grid | |
| Grid = {} | |
| -- Creates a grid with the given tile dimensions | |
| function Grid.init(width, height) | |
| gw = width; gh = height | |
| gr = gh/gw | |
| -- gx and gy make sure the coordinates of the tiles are in line with the drawn grid, and also set the origin in the middle of the screen | |
| gx = WIDTH/2 | |
| gy = math.floor((HEIGHT+gr*(WIDTH+2*gw))/(2*gh))*gh-gr*(WIDTH/2)+.5*gh -- :S | |
| GRID = {} | |
| end | |
| -- Draws the isometric grid | |
| function Grid.draw() | |
| stroke(210) | |
| strokeWidth(1) | |
| yshift = math.floor(vy/gh)*gh | |
| xshift = math.floor(vx/gw)*gw | |
| local i = gh-yshift | |
| while i<=HEIGHT+gr*(WIDTH+2*gw)-yshift do | |
| line(-gw-xshift, i, WIDTH+gw-xshift, i-gr*(WIDTH+2*gw)) | |
| line(WIDTH+gw-xshift, i, -gw-xshift, i-gr*(WIDTH+2*gw)) | |
| i = i + gh | |
| end | |
| end | |
| function grid(p, q) | |
| return GRID[p.."/"..q] | |
| end | |
| --# Tile | |
| Tile = class() | |
| tiles = {} | |
| function Tile:init(p, q, col, wall) | |
| self.p = p | |
| self.q = q | |
| self.col = col or 'gray' | |
| table.insert(tiles, self) | |
| if wall==true then GRID[p.."/"..q] = 'wall' end | |
| end | |
| function Tile:draw() | |
| local x, y | |
| x, y = getxy(self.p, self.q) | |
| fill(getColor(self.col)) | |
| noStroke() | |
| diamond(x, y, gw, gh) | |
| end | |
| --# A_star | |
| -- Finds shortest path from (p1,q1) to (p2,q2) using an A* algorithm, excluding diagonal movement | |
| function findPath(p1, q1, p2, q2) | |
| local closedset = {} | |
| local openset = {} | |
| local i = 0 | |
| openset[1] = {p = p1, q = q1, g = 0, f = heur(p1, q1, p2, q2)} | |
| while i<=500 do -- Limits no. of iterations for security | |
| i = i + 1; | |
| local cur = table.remove(openset, 1) | |
| table.insert(closedset, cur) | |
| -- Checks if goal is reached | |
| if cur.p==p2 and cur.q==q2 then | |
| return reconstructPath(cur) | |
| end | |
| -- Checks four adjacent tiles | |
| for j = 0,1.5*math.pi,.5*math.pi do | |
| local P = math.modf(math.cos(j)) | |
| local Q = math.modf(math.sin(j)) | |
| local adj = {p = cur.p+P, q = cur.q+Q} | |
| if grid(adj.p, adj.q)~='wall' and not inClosedset(closedset, adj) then | |
| adj.g = cur.g+1 | |
| adj.f = adj.g + heur(adj.p, adj.q, p2, q2) | |
| adj.parent = cur | |
| table.insert(openset, fPos(openset, adj.f), adj) | |
| end | |
| end | |
| end | |
| print(i-1,'iterations reached') | |
| end | |
| -- Heuristic, estimates the distance between (p1,q1) and (p2,q2 | |
| function heur(p1, q1, p2, q2) | |
| return math.abs(p2-p1)+math.abs(q2-q1) | |
| end | |
| -- Keeps the openset sorted by finding the correct index in the table | |
| function fPos(set, f) | |
| for i,v in ipairs(set) do | |
| if f<=v.f then return i end | |
| end | |
| return #set+1 | |
| end | |
| -- Checks if a tile is already in closedset | |
| function inClosedset(set, tile) | |
| for i,v in ipairs(set) do | |
| if v.p==tile.p and v.q==tile.q then return true end | |
| end | |
| return false | |
| end | |
| -- Reconstructs the shortest path from parent tiles, starting with child | |
| function reconstructPath(child) | |
| local path = {} | |
| for i = child.g,1,-1 do | |
| path[i] = {p = child.p, q = child.q} | |
| child = child.parent | |
| end | |
| return path | |
| end | |
| --# Functions | |
| -- Functions | |
| -- Draws a diamond | |
| function diamond(x,y,w,h) | |
| pushMatrix() | |
| translate(x,y) | |
| scale(1, h/w) | |
| w = w/math.sqrt(2) | |
| rotate(45) | |
| rectMode(CENTER) | |
| rect(0,0,w,w) | |
| popMatrix() | |
| end | |
| -- Retrieves tile coordinates | |
| function getpq(x, y) | |
| local p, q | |
| p = math.floor((gx-x)/gw+(y-gy)/gh+.5)+1 | |
| q = math.floor((x-gx)/gw+(y-gy)/gh+.5)+1 | |
| return p, q | |
| end | |
| -- Retrieves room coordinates | |
| function getxy(p, q) | |
| local x, y | |
| x = (q-p)/2*gw+gx | |
| y = (q+p-2)/2*gh+gy | |
| return x, y | |
| end | |
| -- Draws a colored tile | |
| function drawTile(p, q) | |
| local x, y | |
| x, y = getxy(p, q) | |
| noStroke() | |
| diamond(x, y, gw, gh) | |
| end | |
| -- Retrieves color from name | |
| function getColor(col) | |
| if col=='gray' then return 127 | |
| elseif col=='red' then return 255, 0, 0, 255 | |
| elseif col=='green' then return 0, 255, 0, 255 | |
| elseif col=='yellow' then return 255, 255, 0, 255 | |
| elseif col=='blue' then return 0, 0, 255, 255 | |
| elseif col=='violet' then return 255, 0, 255, 255 | |
| elseif col=='orange' then return 255, 127, 0, 255 | |
| else return 0 end | |
| end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment