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

Comments

Post a Comment

Popular posts from this blog

Advice needed on tilesets...

I need some advice on which is the best way to handle building the dungeon. Right now I'm using prefabs for my dungeon, they have a north south east and west section for each "room": The basic tileset. This has several advantages, and also several disadvantages. Firstly I can have curved rooms, I can have tunnels and other interesting shapes. The tilesets can look quite nice with a little work. On the other hand I can't easily get the navigation data before building the map and once the map has been built I can't make changes to the layout, like having active pit traps or believable secret doors. Although the rooms are interesting, they are quite repetitive, and it takes a lot of effort to make even a few different variations. Also rooms are constrained to one size. A newer version of the tileset with a lot of variant parts for making more interesting rooms. To create a tile set is a real headache too. Planning how to lay out the UVs, trying to cra...
7 comments
Read more

Upstairs / Downstairs.

I've decided to make my prefabs multilevel. Later this should allow me to add pit traps and other great stuff. It also makes it easier to line up stairs so that you can exit them on the same co-ordinates where you entered them. The prefab editor is pretty much finished, it just needs some code for loading up prefabs from a saved dictionary, so that they can be checked or edited. The entries will need to be forwards compatible, so I'll be loading each tile and then translating the indexes to a new array, that way if I add extra indexes or extra info (like traps or puzzles) I'll be able to update existing prefabs to work with the new standard. Click for a video.
6 comments
Read more

Video Diary 8

Things are moving along well, there's been a lot of progress on the action manager side of things. Actions have finally moved to the UI, so you can initiate actions by clicking the appropriate button. I've set up some dummy actions to show what happens visually when actions are taken, but the actual dice rolls and such are yet to be integrated. The UI objects are also being added, though some are non functional or empty at the moment. Click on the image to see this week's development video. Every time I add something big I also add about a dozen small things. Like the selection box visualization. Previously this was using render.drawline, and old fashioned Blender function which can be impossible to see at certain resolutions, or at certain frequencies. I replaced it with a function that adds planes of the right size and scale in the right location. I also made all characters a little bigger. I still need to do some work with vectors and final target locations t...
3 comments
Read more