Quick Links: Download Gideros Studio | Gideros Documentation | Gideros community chat | DONATE
finding nearest waypoints in a grid/tilemap? — Gideros Forum
  • Home
    • ›

    finding nearest waypoints in a grid/tilemap?

    piepie Member
    edited May 2017 in Game & application design
    Hi, I could use some help figuring out the best (fastest) way to do this:

    I have a grid where I placed some waypoints (see attachment):
    in each coloured "square" (waypoint) I wrote every info I have about it:
    coord x, coord y | #number of tile (counting 1 on the top left, and 416 (width 16*height 26) on the low right corner).
    I also know the grid width and height (how many tiles are there).
    Starting from the blue waypoint ( ["92"]= {7,8} ), I need to quickly find the first occurrence in each direction (the green ones) and then output a table with 4 (or less) indices

    my table currently looks like this, but I could change its structure:
    wptab = { ["23"] = {7,2}, ["46"] = {7,4}, ["87"] = {2,8} ... ["200"]={7,17}, ["262"] = {7,22} }


    Do you have a smart idea to help me sort this out?

    Thank you :)
    +1 -1Share on Facebook

    Comments

    • talistalis Guru
      edited May 2017
      Ok let us do a brain storming together. First let us write down the facts

      -Actually we have four arrays of unsorted random colors starting from your blue starting location.
      -As starting location can always change your 4 array sizes can always change and not fixed size. (up,down,left,right)
      -We want to find the first occurrence of green color in those arrays.

      As our arrays are totally random and we want to find the first occurrence of the green color the only way seems a linear search. Just write a function and in a loop check all elements of those arrays one by one. Whenever you found the green color, save the coordinate and break the loop and repeat this procedure four times for up,down,right and left.

      If your job is to find the count of green boxes we can optimize the search algorithm maybe but in this case linear search seems logical to me.
      +1 -1Share on Facebook
    • talistalis Guru
      edited May 2017
      In addition maybe i didn't understand the logic so much but there seems a problem in your grid image that you posted.
      According to your logic : #number of tile (counting 1 on the top left, and 416 (width 16*height 26) on the low right corner.

      Your number of tile calculations should be like this.
      Ex:You said #87,#88 to the orange ones but they are actually #114 and #115 ...
      gridcorrected.jpg
      481 x 566 - 215K
      +1 -1Share on Facebook
    • piepie Member
      Thanks @talis, yes you're right the tilecount in my image is wrong! I'm really sorry #-o
      actually I don't need to find the green ones because they are green, they are green because I need to find them :)
      Every coloured cell is a waypoint, imagine that the player selects the blue one (but he may also select another one): I need to show him only the next waypoint in each of the four directions, out of a table that contains information about every pictured waypoint.

      I thought of this:
      split the table in 2, both containing the starting(blue) tile:
      table X containing all the tiles on the same y coord of my blue tile
      table Y containing all the tiles on the same x coord of my blue tile

      then sort them by value and see at which index my blue tile is, and then extract the nearest indices to my blue tile, which should be my green tiles.

      However this just seems too much "work" for a thing like that, what do you think? :)


      Thank you
      +1 -1Share on Facebook
    • antixantix Member
      edited May 2017
      In the example below there is a 10x10 grid of cells. Each cell is either empty (0), contains a waypoint (1), or is an edge (2).

      To find the nearest waypoints in all four directions (l, r, u, d) it calls findWaypoints(x, y) where x and y contain the x and y position of the hero in the grid.

      findWaypoints(x, y) returns a table containing the locations of the nearest waypoints (col, col, row, row). A zero means that there was no waypoint found in that direction.
      local wptab = {
-- 0 = empty space, 1 = waypoint, 2 = edge of map
 
-- 1 2 3 4 5 6 7 8 9 10
  {2,2,2,2,2,2,2,2,2,2,}, -- 1
  {2,0,0,0,0,0,0,0,0,2,}, -- 2
  {2,0,0,0,0,0,0,0,0,2,}, -- 3
  {2,0,0,0,0,0,0,0,0,2,}, -- 4
  {2,0,1,0,0,0,1,0,1,2,}, -- 5
  {2,0,0,0,0,0,0,0,0,2,}, -- 6
  {2,0,0,0,0,0,0,0,0,2,}, -- 7
  {2,0,0,0,1,0,0,0,0,2,}, -- 8
  {2,0,0,0,1,0,0,0,0,2,}, -- 9
  {2,2,2,2,2,2,2,2,2,2,}, -- 10
}
 
local function findWaypoints(x, y)
 
  local wayPoints = {l = 0, r = 0, u = 0, d = 0}
 
  local done = false -- find left waypoint
  local c = x
  local row = wptab[y]
  repeat
    c = c - 1
    if row[c] == 1 then
      wayPoints.l = c -- found waypoint so stop checking and save result
      done = true
    elseif row[c] == 2 then
      done = true -- found edge so stop checking
    end
  until done
 
  done = false -- find right waypoint
  c = x
  repeat
    c = c + 1
    if row[c] == 1 then
      wayPoints.r = c
      done = true
    elseif row[c] == 2 then
      done = true
    end
  until done
 
  done = false -- find upper waypoint
  r = y
  repeat
    r = r - 1
    local row = wptab[r]
    if row[x] == 1 then
      wayPoints.u = r
      done = true
    elseif row[x] == 2 then
      done = true
    end
  until done
 
  done = false -- find lower waypoint
  r = y
  repeat
    r = r + 1
    local row = wptab[r]
    if row[x] == 1 then
      wayPoints.d = r
      done = true
    elseif row[x] == 2 then
      done = true
    end
  until done
 
  return wayPoints
end
 
local wayPoints = findWaypoints(5, 5)
 
print("l=".. wayPoints.l, "r="..wayPoints.r, "u=".. wayPoints.u, "d=".. wayPoints.d)
      It's not the best solution most likely but it seems to work ;)

      Likes: pie

      +1 -1 (+1 / -0 )Share on Facebook
    Sign In or Register to comment.