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

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 :)
gridquestion.png
854 x 469 - 23K

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