Construction Valid Ground Slopes

[kmcguire]

I was at the point where I have planned what to build and the general area of where to build, but now I am looking at knowing what is a valid location to build. I could spend a hour or a day doing it the hard way and likely making a few mistakes. Also, I know of the engine callback that can provide a valid build location. But, since my AI is async to the game engine making those calls is more expensive. So I wanted to do it my side (not using game engine). And my point about making mistakes is in reference to going ahead and asking here which could save me some time and headaches.

And, this could help anyone else out there who comes to the forums and needs to determine this. I searched the forums using "construction+valid+location" but not results that I can find. Please, post back if there is already existing information in the forum and link to it.

And, yeah. If you use the callback for the game engine to tell you where to build you can talk about that too even thought I said I wanted to avoid using it. We can still pool some information in here.

I might figure this out before anyone posts, but do not let that stop you from speaking the obvious. For obvious to you is not always obvious to me. And the method I figure out might not actually be the best. I have had that happen a lot.

<edit> Oh, and also doing it my side gives me more solutions to evaluate, right? I think.. Having to work this part out right now</edit>

[imbaczek]

the algorithm is very complex and may change in the future, e.g. by giving lua control over the return value. i strongly advise against reimplementing it yourself. the only suggestion i have is to make a wrapper returning a future/deferred value and work around the problem.

if you want a go at approximating results of this function, take a look at UnitHandler.cpp:308, TestUnitBuildSquare method.

[kmcguire]

You are my hero! That was exactly the information that I was in need of. I completely agree with you. Trying to be perfect in the validation of a building site on the client side is going to be impossible. Like, you said, an approximation could be very useful and I think it shall be indeed. What I think I want to do is build approximations and these can get me into the ballpark, like you hinted towards. It might be almost perfect or a good ways away, but in the end I can use the approximation and let the game engine actually give me an exact spot that is valid at the point in time.

The game engine only had functions for finding the nearest valid build location. This is great, but for most of my computations I want to see the entire map's valid locations for a specific unit. Then apply other factors to reduce all these possible locations to a lesser set of locations. These factors that reduce the locations are such things that relate to the chance of the enemy destroying the unit and how productive the unit would be at this location.

But, before I could get to that I need to have the big picture. The game engine did not provide a big picture and the algorithm for proving the big picture is not extremely simple and is subject to change. So what I want to do is try my best to approximate valid build locations and then to be absolutely sure I plan to ask the game engine for a valid build location nearest to the chosen approximated valid build location.

Each unit has a XSize and ZSize in units (not absolute scale). And, the border of this area defined has the average height calculated. So this means that we have to build a bitmap for each unique combination of the XSize:ZSize. Since changing one by even a little could make a center spot invalid.

So I take the XSize:ZSize and test every point in the entire map for it to be valid. I have to test for:

1. too close to a non-reclaimable feature
2. too close to a unit not owned by my team (since we can not _make_ it move)
3. too close to an existing non-movable unit (since we can not _make_ it move)
4. not too deep in water at any point of the construction area
5. not too shallow in water at any point of the construction area
6. and, if it requires a specific spot like a geothermal vent that we are not too far from this feature point

When the bitmap is generated we use (1), (4), and (5). During run-time we can evaluate for (2), (3), and (6). Since (1), (4), and (5) are for the better part static. I may use (6) to generate a separate map but that might not be needed.

The map can deform, but from what I can tell that either the original height or the height produced by deformation can validate a position. It seems like I could ignore the deformation at first in the event I can not come up with a method to handle this with out eating a lot of CPU, and if my AI really wanted to build somewhere I could ask the game engine for picking the exact spot even though my approximation showed it to be invalid.

You guys see any potential problems? Any reply is welcome. I will not reply to defend it. Just want to get a heads up. And, to recap:

I will use approximations only to a rough idea where to build, then ask the game engine for a finalization of that position (nearest valid location during run-time).

Also, the memory consumption and time to generate these bitmaps are not going to be a problem. I have done the same using the unique slope values of all units for each team. Since I am threaded I can slowly work on it in the back ground and use approximation for stuff I have not yet computed. If memory consumption is a problem (either in the prototype or production) I have some methods to hopefully curb it enough I think.

Thank you, Imbaczek. The pointer into the code was very helpful. It would have likely taken me hours to find it.

[imbaczek]

sidenote: for future reference, it's actually pretty easy to find the code you can ask the engine about - it's all in the ExternalAI/AICallback.cpp. from there, it's only a few "go to definition"s away from what you need.

as for the algorithm, as long as you double-check for false positives, you should be fine. memory usage should be negligible (several megs for the largest maps if using a bitset.)

[kmcguire]

I got this to work, but I spent a lot of time optimizing the algorithm. I originally wrote it in Lua which worked well. However, it was very slow and extremely expensive with memory since Lua has no efficient array object (and never should have one for it's purpose), but that is beyond the point. So I implemented a C array and wrapped it with a Lua table which fixed the memory consumption, but was still slow.

I in the end had to write it in C, and it still takes a significant amount of time to generate the maps. It did solve the memory consumption completely. And, I can access it in Lua using the wrapper for C arrays. But, I will move forward with my project and come back later and do some more optimizations for speed which likely will just degrade the resolution of the maps. For prototyping my AI this is a success.

I used bits to represent if something could be built or not build (0 or 1).
Using the modification NOTA, on the map Tale_of_Two_Hills-v01:
129 Maps (129KM per map) Giving 16.26MB Total For All Maps
And, if you compress than and store as cache you will have a total size of roughly 700KB.

So, if you go this route you will have to deal with finding a elegant solution to the CPU time used when generating the maps for the first time.

I attach neat map of output for a unit definition with XSize:ZSize=6:6, MaxHeightDif=7.05, IsFloater=1, MaxWaterDepth=0, MinWaterDepth=11. (Yellow is invalid-build area, Black is valid-build area)