Hey everyone, I'm working on the AI of my RTS. I got some nice classes (managers) which should distribute the tasks of the AI. Not much code yet, though. My first priority ist ohave the AI build objects on a semi-decent place. Unfortunately, my buildings need to be placed (freely) next to a road. I can't figure out exactly the best method to do this though. What I have is: - Individual towns/cities, each with their own road network (kinda like transport tycoon) - Knowledge of the indivual road tiles. - Buildings placed in the town. There is no grid. Objects are placed freely in close proximity to the road. The goal is to: - Find a free spot ( on either side of the road) - (- Determine if it's tactical suitable, if not, find another spot) - Or build a road. now, building a road shouldn't be too much of a problem, I think. But the problem of how I would find a free space, while the town exists of more than just "one single road", because it has crossings and everything. While typing this (really helps sometimes, typing out the problem :P), I'm thinking of a virtual grid (the size of the road), and to 'fill in' the objects that have been placed. I guess I could search for an appropriate sized open block of tiles to find a suitable place. What do yo people think of it? Or do you have any other suggestion or experience? Many thanks!

randomly walk the road mesh/tiles and sample 10-15 spots to see if you can build there. of the successful positions, chose the one with the best tactical position. you could also walk the road from best tactical position to worst and place the building at the first free spot. the former will get you more randomness in your AI base construction (not the same every game), the latter will result in fairly deterministic bases.

if no spot is found this frame, try again next frame.

If after 5 frames no spot has been found, fail the build and construct a road.

-me

I am not sure I understand fully your problem. From what I read, you have buildings, presumably rectangular when viewed from the top, and you want to find a free spot to put a new building of a known size.

Now I don't know the density of buildings in your map, if it is not too dense, Palidine solution is probably a good one. You will probably think that it is not the optimal solution because it can leave empty spaces between buildings and fail to fill the area, but I just wanted to give you the advice not to spend too much time trying to find an optimal solution : this is (as far as we know today) a NP-complete problem.

I think your grid solution is a good one, you could use it when Palidine solution fails, before trying to build a road.

Question : do you have to build a road on an empty space or can you destroy a building for this ? if not, your grid solution may end up "locking" your road with buildings on each side.

Well, I guess a "brute force" would work, by casting rays down or something. (Otherwise I'd end up on the grid again).

But yes, I need to determine where to place the buildings, next to a road or build a new road and place it next to it. Since the road is a lot smaller 'tile' I'm concerned that brute forcing it won't work.

I guess I might give it a go though.