Skip to main content

RTS pathfinding

I spent some time today looking at the possibility of adding A* path-finding to my game.

I've used it in the past and I actually got it running pretty fast, even though it's written in python. So I was optimistic about replacing my less than stellar dumb path-finding with A*.

However I ran in to some problems.

First is the fact that I'm working with quite a fine graph, each infantry man takes up one tile, and tanks and the like take up several (a big tank takes up something like a 12x12 chunk of tiles. When you're working with a graph which might be several hundred tiles square, you get slow performance.

When I've used it before I worked with either a pretty course grid, or with navigation nodes.

[a* with grid]

[a* with nodes]
Both these situations give you quite a limited grid and so, good performance.
Working outdoors with such a fine and almost unlimited grid makes the algorithm work too hard, especially when you have a lot of agents.

Looks like I'll have to think more about this. One option would be to use a course grid or node array alongside my fine grid path-finding. That way the agents are just finding their way from one node to another. The curse grid could take in to account such things as rivers and buildings while ignoring vehicles and infantry. If the way to the next node is blocked the agent would just wait for the blockage to clear using the right of way system I mentioned last time.

In fact this is something I prototyped around 2 years ago, using node based a_star path-finding and a path smoothing algorithm.

[node path and smoothing]
When I watch these old videos I'm tempted to go back to the solution I was working on then, which wasn't tile based at all, but free form using beziers. Unfortunately I could never get the problems with colliding agents solved and the result often ended up with troublesome traffic jams.

I think I'm going to leave this for now though, as this doesn't form a part of the basic agent movement actions, rather a part of agent behavior, which will be controlled by the agents finite state machine. The agent can continue to use the dumb pathfinding, and a* will be used to supply some intermediate waypoints when long distance movement is required (by breaking down the agent destination list in to reachable steps).


Popular posts from this blog

Back to Vinland.

I'm going back to my real time tactics project, Vinland 1936.
While working on the other project I overcame the problems which were stopping me from saving/loading the game and also cleaned up the base code a lot.

After a few weeks I'm getting near the the state I was in before.

Infantry are back to their previous state, and vehicles are running OK.
This time I'm going to push ahead with mocking up the combat system though before I work any more on the vehicle builder or graphical aspects of the game.


I finished working on the code for adding foliage and having some extra time I decided to experiment with the code for rockets.

The original idea I had was that rockets would be large vehicle components that can be fired very quickly, regardless of how much manpower is used for reloading.

They would use up a lot of ammo, so they would run dry after a short but devastating barrage.
The problem here is that it's easy to take advantage of this by adding a lot of ammo, which is much smaller than in bulk than the rockets.

There's also the problem of firing large caliber rockets. In real life rockets of up to 30cm were used, but I think that will be too powerful for the scale of combat in this game.

lol. Somehow that one trooper survived the mother of all explosions...

A 30cm rocket could contain nearly 30KG of explosive. That would be a very large explosion.

I've tried to balance the game by using a simple equation to make bigger guns more powerful, but hopefully not too powerf…

Infantry combat and entering buildings.

I've been working a lot on the game recently and I've nearly rebuilt it to the level it was before. Past that maybe, since now I have the beginning of a working combat system and the ability to save and load the game.

Infantry can now occupy a building. It's quite an abstract representation, since they stay at the door and turn invisible. But they can then fire from one of the windows and take damage from shots at the windows too. I think I've set it up well so that when building damage and destruction is working then the system should continue to work.

For combat I tried some new ideas, but they didn't work out that well. It seems that it's important that viewing range should be further than shooting range. Now shooting range is pegged at 18 units of distance, while viewing range can extend out past that.

In the above image one unit has an officer, so has further viewing range. The other can only see as far as they can shoot, a dangerous situation since the en…