finding nearest waypoints in a grid/tilemap?

pie

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

talis

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.

talis

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

pie

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

antix

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