Jump to content
  • Advertisement
Sign in to follow this  
ajoling

[RTS AI] Road placement

This topic is 4429 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!