Finding the nearest positive integer in a 2-dimension array

[hach-que]

With all the help from #lua, I've managed to load all the values of how much metal there is in a position into a 2D map (excluding locations where there is no metal, to speed up the search process), but now I need to get the nearest position in that 2D map (2-dimension array) based on a unit's location.

How can I do this (I know it's going to involve some complex math)?

[KDR_11k]

Put it into a tree and search?

[hach-que]

I checked the WIKI and the Lua documentation, and I don't understand what you are referring too. Can you provide a link?

[Evil4Zerggin]

I've actually done the same thing before.

Specifically from my gadget:

Code: Select all

46	local metalMapScale = 16

...

168	local function GetMetalMapCoords(posX, posZ)
169	  return math.floor(posX / metalMapScale), math.floor(posZ / metalMapScale)
170	end

So just divide the (x, z) coordinates by 16. Although I suppose one could use math.round instead of math.floor for strictly the nearest spot.

[imbaczek]

complex math no, but it's a tricky problem to do in Lua due to its relative slowness. IMHO the best simple solution would be to precompute distances to your nearest point during widget initialization - in pseudocode:

Code: Select all

for x = 0..map width:
  for y = 0..map height:
    nearest_spot[x][y] = find nearest spot

find nearest spot(x, y):
  for r = 0..some max value:
    search for a spot on an outline of a square centered on (x,y) with side length = r

the basic idea is to try squares at increasingly higher distances, somewhat like an explosion. this will take lots of memory, though. there are tradeoffs to consider and also various approaches to make this algorithm better in a lot of ways.

[hach-que]

I've actually done the same thing before.

Specifically from my gadget:

Code: Select all

46	local metalMapScale = 16

...

168	local function GetMetalMapCoords(posX, posZ)
169	  return math.floor(posX / metalMapScale), math.floor(posZ / metalMapScale)
170	end

So just divide the (x, z) coordinates by 16. Although I suppose one could use math.round instead of math.floor for strictly the nearest spot.

I don't need to convert metal map X,Z coordinates into movement X,Z coordinates, I need to find the closest point of metal (Except that it must be done fast).

complex math no, but it's a tricky problem to do in Lua due to its relative slowness. IMHO the best simple solution would be to precompute distances to your nearest point during widget initialization - in pseudocode:

Code: Select all

for x = 0..map width:
  for y = 0..map height:
    nearest_spot[x][y] = find nearest spot

find nearest spot(x, y):
  for r = 0..some max value:
    search for a spot on an outline of a square centered on (x,y) with side length = r

the basic idea is to try squares at increasingly higher distances, somewhat like an explosion. this will take lots of memory, though. there are tradeoffs to consider and also various approaches to make this algorithm better in a lot of ways.

The problem is when the user creates new construction units or the unit moves; the distances will no longer be correct.

[Licho]

It will be.. you will precalculate position of nearest metal spot for every map spot..
This wont change unless metal map change..

Only problem is if you actually need nearest uncapped metal - then your precalculated data are no longer valid..

Also you can check AI's they certainly do this..

Imo the easiest is to search in circles around your position till you hit metal (if you only need nearest metal spot and not the best optimized place for metal extractor on general map, which is actually very complex problem :)

[hach-que]

I suppose I can do the search circle method, and then search connecting metal positions for the highest amount of metal in that spot.

[Evil4Zerggin]

Ah, I see what you mean now. As a first approximation, I would try something like this:

1. Make an boolean array of size mapSizeX / 16 times mapSizeZ / 16 (the metal map has a resolution of 16 elmos). Elements are true if the map has metal in that spot. Also make an empty list.
2. Look through the array. Whenever you find a element that is true, add the x and z coordinates to the list, then set all elements within extractor radius of that element to false. This will give you a list of mex spots.
3. When you want to find the closet mex spot to a point, go through the list and find the closest spot.

This would probably work fairly well for maps with discrete metal patch; since most maps don't have a ridiculous number of metal spots and the extractor radius is generally quite a bit larger than the size of the metal spot itself. The cost per search shouldn't be too bad--one distance calculation per metal patch. I suppose one could try to optimize by splitting the map into sectors, for example, but I don't think it's worth it for most maps.