[AI] Finding a point valid for shipyard construction

[Fingolfin]

Hello everyone! I've been posting quite a few threads lately, but i've run into a few tasks i've never had to deal with before, so here it goes.

I am trying to make a custom-made AI for a map, and so far it is looking really well. My only problem right now is, when ordering an AI worker to build a shipyard, i don't know where you can and cannot build it.

With other structures, it is easy to just test a number of points in a circle around the workers location to find one where it fits, but with a shipyard it ain't so simple, as it has to be placed at the shore. My first thought was to place a kind of dummy shipyard at the workers location, hoping it would snap to the nearest pathable point, like units sometimes do so that i could trace its new location. This did not work however, and instead i just had a shipyard on dry land. Anyone has any good ideas on how to solve this?

 

[Dr Super Good]

There is no simple solution to this and I am sure many professional RTS developers could write entire books on the difficulties involved with AI placement of certain structures with strict building requirements like docks.

It might be a good idea to run this in some kind of "thinking" background task that occurs over multiple game frames to avoid stalling game progression. AI often does this and it is why some times the AI is slow to respond to certain actions.

Firstly you need to find a shore to build the annoying thing. Unless you hard-program all "shore" areas on your map into some kind of searchable list this is going to be a monumental task. If you have such a list you need to search for an area nearby the worker and try to place it there or if that is crowded try one further away.

Firstly you need to find water. If your map is mostly water this will not be a problem however in maps with limited water (maybe a few lakes) it can be difficult. A good way to do this could be a far search around the unit testing for water every 640 units (up to some maximum) in 8 or 16 directions. Once water is found you have a rough estimate where some shore might be so can stop searching.

Then you could start to map the shore using this positional information to try and locate a suitable build location. To do this you will map the entire area shore pathability (maybe every 2 pathing cells, shipyards are big so do not need fine resolution) into a "cell" which you can then perform more precise searches on for a valid placement. The cells is a 8*8 or 10*10 tile unit of mapped space which acts as a sort of image you can test for there being shore. Once your cell is generated you then find any "shore" pathing and then try to see if within the area it makes there is enough space for a dock. If such a space is found you can then issue the other to build the dock. If not then you will need to advance along the coast line (probably requires some normal vector from shore into water) and then map that as a cell and repeat the process. If you hit land during the process (cell with no water) or water (cell with no land) you need to repeat the first process from that new location to find the land water intersection and begin searching there again. To prevent infinite recursion you should give up after enough attempts are made or if you end up near where you already checked.

Since this is a costly process it is recommended to cache the position cells which had good shoreline areas so if you ever need to build another dock or want to rebuild a lot dock you can do so more efficiently by either re-using the previously detected cell or at least starting searching in a promising area.

There is another approach which can be only described as "brute force". Instead of smartly trying to find a location for potential cells using some kind of long search algorithm (find somewhere promising that is vaguely on the border between land and water) you could break the map up into cells and try them until a suitable site is found. This would be done by breaking the map into uniform cells and then when wanting to place a dock you start testing cells in a spiral pattern starting with the one under the unit. Eventually the spiral will find one suitable and you build your dock there. Caching would be recommended for this sort of test due to how resource intensive it is.

Since mapping a cell is likely to be resource intensive I would recommend processing only one or two cells per AI think loop (which executes every few frames). Also after finding a suitable position for a dock you need to test if your builder can actually reach it as the algorithms described above will have no problem finding a suitable location on a nearby island that the builder could never reach.

The above models humans to some degree if you think about it. When you want to place a dock you first look for where water meets the land. You then follow the coast until you find a suitable site. The vision of your screen shows an area of the map which you test for placement which the AI would mimic with a cell. Once you know of a suitable placement area you might re-use it again and again mimicking the cache. The first approach of mapping all shore areas suitable for docks mimics someone with prior knowledge of the map who knows where all docks can be placed so does not need to search for suitable dock sites.

Game AI is a highly complicated area which is probably far too under explored even professionally. Especially nowadays where developers are far too willing to write sloppy AI as they expect humans to constantly fight themselves competitively for a challenge.

 

[Fingolfin]

I agree that AI offer some of the most tricky challanges of game programming, i sincerely respect those who can make good AI without making it cheat shamelessly.

The method i went on trying was to add a few preplaced neutral shipyards in the editor. When the map starts, i loop through them in turn, and add their coordinates into an array after which i remove them. Once i have a neat array of valid building positions, it is easy to loop through it to find the closest. Thankfully, the "issue build order" native returns a boolean informing wether the order was successful or not, so there is no need to look into individual pathing cells - i can just check wether the order succeded or not.

The difficulty of this approach so far is that even though i can find the closest coordinates, i can't know wether they will not be already occupied. Therefore, i'd want to exclude this item from the list and try the search again - although i am not sure how. I guess one way would be to let a dummy unit issue a build order at the location before i accept it as the closest, which would eliminate the need to do repeated searches, but that also seems like a cumbersome solution to me. Another, albeit less accurate solution, would be to test the pathing at that particular point and see if it is non-pathable, which would indicate it being occupied. Any thoughts?

Thank you for your response.

 

[Dr Super Good]

The difficulty of this approach so far is that even though i can find the closest coordinates, i can't know wether they will not be already occupied. Therefore, i'd want to exclude this item from the list and try the search again - although i am not sure how. I guess one way would be to let a dummy unit issue a build order at the location before i accept it as the closest, which would eliminate the need to do repeated searches, but that also seems like a cumbersome solution to me. Another, albeit less accurate solution, would be to test the pathing at that particular point and see if it is non-pathable, which would indicate it being occupied. Any thoughts?

You could also perform an area search at the point and test if one of the units there is a shipyard. If a shipyard is built at such a position you could cache it in the list. You can then check if it is either null or dead to know if the place is free and if so ignore it from the search.

 

[Molaf]

Maybe it's not what you are looking for but .. what about create "regions" where building a shipyard is possible? I don't know how big is your map but wouldn't it make things more simple?
Then if the spot is already occupied, just run a trigger to remove the region from the "availables" spots

 

[Dr Super Good]

Maybe it's not what you are looking for but .. what about create "regions" where building a shipyard is possible? I don't know how big is your map but wouldn't it make things more simple?
Then if the spot is already occupied, just run a trigger to remove the region from the "availables" spots

That was suggested earlier...

Unless you hard-program all "shore" areas on your map into some kind of searchable list this is going to be a monumental task.

They have to be placed in a searchable list so that the AI can try to find an appropriate site. It would be stupid if the AI tries to build a dock on the wrong island or it builds one very far away instead of right next to its base.