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).

Comments

Popular posts from this blog

Make your game models POP with fake rim lighting.

I was watching one of my son's cartoons today and I noticed they models were using serious amounts of simulated rim lighting. Even though it wasn't a dark scene where you'd usually see such an effect, the result was actually quite effective.



The white edge highlighting and ambient occluded creases give a kind of high contrast that is similar to, but different from traditional comic book ink work.


I'll be honest, I don't know if there's a specific term for this effect in 3d design, since my major at university was in traditional art. I learned it as part of photography.


You can find plenty of tutorials on "what is rim lighting" for photography. It basically means putting your main sources of light behind your subject so that they are lit around the edges. It can produce very arresting photographs, either with an obvious effect when used on a dark subject...


..,or as part of a fully lit scene to add some subtle highlights. See how alive the subject look…

How to... build a strong art concept.

So you want to make some art assets for your game. The first on the list is a Steampunk Revolver for your main character to shoot up Cthulhu with. Quickly opening your internet browser you start with a Google image search. Ah, there is is!

It might be a good idea to find a few influences so you don't accidentally end up copying a famous design.


Just mash them up and you're ready to go! Off to your favorite modeling program.
But wait! isn't there more to building a strong design concept than that?

Of course there is.
One of the diseases of modern design is that of recursion. Everything is a copy of a copy of a copy. This is especially a problem with "historical" concepts. Over the course of that recursive process the concept becomes infected with modern design elements, and ends up looking very similar to everything else that anyone else has ever made.
If you want to come up with a really fresh idea, you have to get beyond secondary references and go look at real …

Skynet

Ok, so it's not exactly skynet, but I have got my first AI state working, kind of.


The first state is "HOLD" in which case the agent stays in place where they are and shoots at any unit that comes in range. When I started writing this module, I found that the existing method of triggering actions wasn't good enough to allow the AI to choose the best weapon or target. It worked by simply sending a command to the unit to trigger the currently selected action.

If the action is valid, it triggered, if not it didn't.
That's fine for play controlled units, as that's all they need to do. But AI needs to know in advance if the action is valid. The player can get that info from UI feedback, but that wasn't available to the AI player.

There were three problems:

1. The UI feedback duplicated code in the action trigger function. These  two sets of code could get out of phase so that UI feedback was wrong.

2. The action trigger didn't give enough feedback for …