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)?
Finding the nearest positive integer in a 2-dimension array
Moderator: Moderators
Re: Finding the nearest positive integer in a 2-dimension array
Put it into a tree and search?
Re: Finding the nearest positive integer in a 2-dimension array
I checked the WIKI and the Lua documentation, and I don't understand what you are referring too. Can you provide a link?
- Evil4Zerggin
- Posts: 557
- Joined: 16 May 2007, 06:34
Re: Finding the nearest positive integer in a 2-dimension array
I've actually done the same thing before.
Specifically from my gadget:
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.
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
Re: Finding the nearest positive integer in a 2-dimension array
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:
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.
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
Re: Finding the nearest positive integer in a 2-dimension array
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).Evil4Zerggin wrote:I've actually done the same thing before.
Specifically from my gadget:
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.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
The problem is when the user creates new construction units or the unit moves; the distances will no longer be correct.imbaczek wrote: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: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.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
Re: Finding the nearest positive integer in a 2-dimension array
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 :)
This wont change unless metal map change..
Only problem is if you actually need nearest uncapped metal

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 :)
Re: Finding the nearest positive integer in a 2-dimension array
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
- Posts: 557
- Joined: 16 May 2007, 06:34
Re: Finding the nearest positive integer in a 2-dimension array
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.
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.