Suggestion to random building locations

Hi Zalamander and AIAndy:

- Amai is suffering from random building location. I think if we can find the "Front" or "Opening" from the map, we can put our defensive towers and buildings there.

How to find the "Openings" (see Fig 1.)
When the game starts it could be done during the map scanning moment:
1. Find the coordinations of all the home (Xo,Yo) of ai players (that is town hall/great hall,etc) (function GetDestructablesLoc?)

2. Define how "fine" you would like to scan for the openings. Here I set, say 8 slices. (Note: The more the slices are divided, the more the accuracy a building can be put, but the more the power of CPU comsumption). Then every slice is:
slice = 360/8 = 45 degrees

3. Determine how "far" you would like to scan within the circle. Let say r=600

4. Time to detect. Choose an arbitary position to start. Let's say north to the town hall:

theta = 0
Xp1 = Xo
Yp1 = Yo + r

Scan whether this location is pathable by using PitzerMike's function IsLocPathable (actually AIAndy did this function and Mike made a crown on it). This function is good because it detect all obstacles like rocks, trees, mountains, seas and even cliffs). If it is pathable, then put it into an array and memories it, otherwise forget it.

The second point P2 (Xp2,Yp2):

theta = 0 + slice (ie 45 degrees)
Xp2 = r x cos(theta)
Yp2 = r x sin(theta)

Scan again whether this location is pathable.

The third point P3 (Xp3,Yp3):
theta = 0 + (2 x slice) (ie 90 degrees)
Xp3 = r x cos(theta)
Yp3 = r x sin(theta)

Scan again whether this location is pathable....

end if scanned all 8 slices. The one with a pathable location is the opening.

Q: What happen if there are more than 1 locations are pathable?
A: Then the one nearest to enemies' home should be the "Front" and towers shoud be built there.

I think in general 16 slices is a good number. 32 slices is a "fine" value but could comsume a bit more cpu.

If you think it is not enough accurate then make a new r (say 1000, and then 1500, etc) and do the same process again.

We should now find the "Opening" of the map and put all our buildings around that point instead of our Town hall (by drawing a circle from this center and all random buildings inside this circle, or exactly that point if you need a specific location).

This concept actually could be applied to moving object like moving units if function IsLocPathable changed to other functions like searching for creeps every second, then we could make a path for our dying units which avoid creeps on the way. However, no matter how hard I think I still cannot math it out when it scans and discovers a creep nearby. If anyone knows please drop a word to let me know. Thank you.

If this works then at least we can solve the random buildings problem first.

^_^

Actually what the map scanning does is check for all locations on a 90*90 grid if they are pathable or not.
Unfortunately that does not necessarily give us the info we seek here. If we check in a radius around the start location, the point we hit might be a small area surrounded by trees or it might be a narrow pathway or even only a larger area in the back of our base. And even when we have the correct information where the entry of our base is, taking over the building placement means you have to do the entire base layout and find a place where the building you want to build fits.

Yes... this is an idea I think very demanding. What I intend is:
1. Rewrite the Islocpathable so that it scans only for a spot, not an area
2. Yes, what the function scan could be a small area surrounded by trees or just a larger area in the back. Hence every slice must be as small as possible, but in very large quantity. There are not only 8 slices, but 1024 slices or more, and there must be many radius r, from 500, 600, ... 2000 so as to gather an "image" of the map around the base.

The whole process could be:
For every base,
r=500, scan for 1024 slices
r=600, scan for 1024 slices
r=700, scan for 1024 slices
...
r=2000, scan for 1024 slices

I got this idea from DOS system which consists track and sectors and Differentiation/Integrations in Mathematics, the more you divide, the more you would be accurate.

The more the pathable slices gather together in a area, the more likely it would be the pathway in the front.

If a small area is surrounded by trees, then the area surrounding this area must be inpathable because the trees are inpathable; if there is a large area in the back, then there must be inpathable area when there are many r's, also that area is also not closest to enemies' base (shortest distance between our base and their base), too.

"Accuracy" depends soley on the power of the CPU... I might give up playing if I still want to play with my 1.8G... -_-b

3. No need to do the entire base layout, just replace the base by "front point" or "front area" when making buildings (especially towers). This may help to avoid towers and racial shops built at the back. What I mean is when you find that front area, let ai build randomly in that area, and all buildings built are at least in front of your base.

It cannot make precise building strategies, but it might fix part of the random build bugs (hopefully).... and is all I can think of for this problem... -_-

The check if a certain location is pathable is pretty expensive. Doing that many checks would certainly cause a very noticable check (rather a lag of several seconds if that many scannings are done at each base).
And even with that huge amount of data available (and actually what the map scan delivers should be enough) then you still need to find out where the front is. You got loads of measure points. Let's assume they are on a grid (that would spare us another scan). They are just measure points that each say pathable or unpathable. Now an algorithm is needed that takes that information and efficiently says where the front is.
To only apply that to front line buildings is a good idea but we still need another algorithm that finds a place to build the building in that area (the hard coded AI won't do that for us). And by just building at whatever place it is buildable will give us a certain chance that we do block units in.

I am also worried about the heavy load of check may drag the game, or may even hang it...

I can take sometime to do the intepretation of those huge data. Also I can try to make an algorithm to scatter buildings so that they do not block units...Hmm... your judgement... if you think it may work and not dragging the sytem too much then I shall start working, or if you think it is too expensive then I will stop here and go on to the next suggestion about item sharing system. I found one of the ai heroes got double the same item (e.g. boots, scrolls, etc), while the other did not have that. It would be nice if they could share those items, or even some items can be strategically used on particular heroes....

I have thought about that problem quite some time even before your suggestion. To find the front I actually found a better way. After the map scan, there is a huge 90*90 grid with pathing info. Now a pathing algorithm is run on that that computes the pathing distance from the home base to each point on the grid (and also the path there). Now the path to every enemy base can be taken and followed for a certain distance. The points you get is the front of the base (can be multiple) and since the paths are already computed that is pretty cheap.
You may wonder why I did not tell you of that solution at once. The reason is that I did not want to cut off your way to a possible different solution (and problem solving like that helps to get a grasp on algorithms and efficiency).

But I do not really have a good solution for the actual placement of the building yet (finding a possible space to build it on). The native that is used to issue an order to a peon returns false if that order cannot be done at that moment which is the case if the chosen target place is unbuildable (for a build order like in the case of the building placement). But what pattern to try out one after the other and how to prevent an infinite loop when there is no buildable spot in the area.

Thank you for your consideration! Well actually I just want to find a solution to solve this problem. I would be very pleased when I play the game and see everything working properly, and I don't mind any method anyone suggests. You now got a better and cheaper way, then it should be solved. No more bug is Great! ^_^


I got some stupid ideas. You can see if it works or not:
1. To scatter building so that they don't block units, increase all buildings size by 100-200 when placing them, if there is any functions working this way...

2. Because the front can be found, infinite looping could be prevented by drawing a straight line (imaginary) through the base and the front. Then you can find another "Second Front" that is in front of the first front by using simple trigonmetry (2 point form? I can't remember). So when say 3 times ai cannot find a place in the first front, go on to the second front...

I had this idea before I made that DOS and differentiation thing, but it didn't work in that case because many times the map would be "upside down" (that is the opening direction opposite to the direction to enemies). However it could work in this case, maybe...

^_^

The idea with the greater building is very good. There is only one problem with it. I don't think there is a possibility to increase that size ingame. One possibility would be to divide the buildings up into size classes and for every size class choose a building that is slightly larger for finding the place to build at.
Then the same trick could be applied that I use for finding a place to build the expansion. Using the CreateUnit native creates a unit/building at the next possible location where it can be built from the given location. So one could give the chosen front point and then use CreateUnit with the larger building to find the correct point to build. Then remove the created unit and order a peon to build at that point the real building.
All that together should hopefully work quite fine and give us the building at an acceptable position with acceptable programming time and efficiency.
Of course that means having to create the size classes and finding a good bigger building for each size class and then putting all that info in a table. As an alternative the bigger building could be written directly in the unit table for each unit and no size classes. I guess what to use depends on how many size classes would be necessary.

Hee... I remember you have applied a similar trick on previous verions, which build about 9 imaginary buildings around the base, making the area bigger... ;P

I think human buildings should be closely packed as they used to be, that is human towers and farms should not be replaced by bigger buildings as they are used to defend, more space means more enemy melee units can surround and causing them more damage, while barracks could be a bit loose because they are used to produce units. Ne, on the other hand should be a bit loose for all buildings. I am not sure undead and orc because some of them building loosely and some packed altogether.

I wonder if there is any relationship on distance between our base and enemies base, and the closeness bewteen our buildings. I have a feeling that the closer the distance, the more packed the buildings people build... Maybe wrong...

Anyway, good! good! bugs away! :D