RTS game tools experiements.

Game Engine Works in Progress and Game Demos
21

A* is running well, it’s quite fast and produces adequate routes through even complex groups of obstructions.

I’ve recently added a path smoothing routine. It gets pairs of points on the route produced by A* and checks if they can be joined. If a clear path exists between them it pops the unnecessary middle point and starts again. I’ve experimented with several options such as more or less connectivity for the waypoints, optional smoothing (for maps with a lot of obstructions it can be turned off) and I’m also working on one other important addition: A* request queuing.

If many agents run the A* routine at the same time it can result in a noticeable pause. But if add a pathfinding request manager and I queue the requests I can stagger how they are processed over the course of half a second or more. This is a long time in game logic terms (30 logic tics) but it’s not that noticeable to the player, especially as the agents nearest the goal will start to move almost immediately, while those far away will be waiting for space to be cleared up anyway. The result is that the small spikes caused by running the A* routine will be swallowed up in the excess processing power that’s usually available. The game should continue to run at 60 frames per second without any pauses or slowdowns.

22


Didn’t do anything yesterday.
Today I added some code to cope with rotated and scaled obstacles (before you had to count on the user having applied scale and rotation to all the obstacles before they ran the game, a recipe for false bugs) I also split the obstacles in to obstructions(yellow) and hindrances(magenta).

Obstructions are buildings and rocks and very thick clumps of trees. No agent, not matter how adept can move through them.
Hindrances are things that hinder your movement. Sticky mud, sparse trees, shallow water, etc… If an agent has the “all_terrain” property it can move through the terrain but at a reduced speed. other agents will get stuck in such terrain so they can’t enter.

This allows things such as infantry trying to swim a cross a stream, or move through a forest. It also allows difficult winter or desert terrain. The A* routine will still try to find a way around such hindrances, preferring a bridge if it is close to the crossing point, or trying to take a path through a forest. On the other hand, if you feel the need you can over ride this behavior by manually ordering the agent to go through the terrain, which will avoid the A* check. For example if the bridge is mined, or there are infantry ready to mount an ambush in the trees.

Finally I modularized the code for the A* initiation and moved it over to my bgeutils.py script so from the main movement script you only have to run:

import bgeutils
bgeutils.navigation_initiate(own)

and it will create the required properties on your AI control handling object. This is part of my drive to clean up my projects, moving things in to a back area where they can do their thing without me having to scroll through them to get to the next big function. Right now I only have the single utility script, but I may use different scripts for different functions, such as AI, Movement, Effects etc… However, there comes a time when scrolling through a couple of hundred lines of code is no more confusing than switching back and forth between 20+ different scripts, some of which overlap in function.

I hope to finish the movement scripts this week, testing them out on a fully 3d map with buildings and difficult terrain.

It’s my goal with this project to concentrate on game design and mechanics and leave the art assets until later as much as I can. Once I have a working game I can relax and start working on visual side.

Today I was thinking back over my past attempts at AI for Blender. One of the first I designed was this one:

It was nearly all made with logic bricks, with about 15% done with python (mostly stolen from other people’s game demos). This was in 2010, when I first started coding. Looking at it now, it’s not that bad. Functional and surprisingly fast for a system that relied on rays and radars. Sure the agents often crash in to each other or in to buildings, but it’s not bad considering. :slight_smile:

23

Great stuff! I look back at my scripts when I first started a year ago and…cry a bit. I can’t wait to see all this running in a finished level.

24

I definitely would like to try this out, my terrain will not be random, however it will be made of modular construction pieces, and will not be easily navmeshed without crazy amount of calculations,

I wonder if you could do a “pre A*” to cull out tiles that are not to be used to navigate?

25

Sure, there are a few tricks I could try yet, but most of them work best with grid based a*. The problem is that grid based a* pathfinding is already much slower than a node based one. Node based pathfinding however, suffers from reduced connectivity compared to grid based.

If I try to cull some nodes it further reduces connectivity. I could try culling some of the obstacles. Thats something I need to try.

26

integrated_a_star.jpg606×1023 556 KB

Today’s progress.

I’ve ported the A* over to the agent movement and orders script. Now I can order agents around and have them avoid the obstacles. You can see the effect of reduced connectivity here, all the agents are sharing a similar route, so they shuffle in to single file. Not very tactically smart, so the Ai is maybe going to suffer if I don’t do something to counter that.

One thing I can do is to block routes which are in use, encouraging other agents to go a different route. I’ve put some of the code in for that, but not tested it yet. It might need to be that, if 6 or more agents already share a node as their current target we can consider it blocked for other agents, so they will try the next best route, until that one is blocked too. Otherwise moving a lot of units at once will lead to them spreading out all over the map.

Another thing I can do is to add more nodes. Currently the frame rate drops to 55 FPS when a large number of agents are given A* routes at the same time. I think I can improve that performance with the A* queue I talked about earlier.

There are also some other misc fixes that need to go in. Such as having long route and short route, and getting rid of bezier curved routes, as they either take a very long time to check for collision, or can cause accidental collision if not checked properly. Plus it’s strange to have curved routes for non-A* movements but not for A*.

Another test I want to do is to see if I can get any speed improvements by culling obstacles which don’t overlap their bounding box with the bounding box of the proposed route. This will take extra time to perform, but should speed up intersection and selection checks a lot when calculating short routes. Checking if bounds overlap is much quicker than checking if a vector passes though one of up to 5 lines which make up a square of the same size. I’ve precalculated the bounding boxes as part of the obstacle dictionary.

bounds.jpg606×606 124 KB

It is immediately obvious that there would be some benefit to breaking the largest obstacle up in to smaller parts to allow culling to be done.

Finally I need to do some work on where the destinations are calculated. So that they don’t generate inside a building by accident. But I need infantry to be able to enter buildings, which i think I’ve found a fix for.

So far I’m enjoying the result of separating the scripts in to utilities and major functions, it makes it much easier to keep track of the outline of the code.

You can see the result of one of my utilities, my own draw_line script. It uses objects not rendered lines, so it doesn’t have to be redrawn every frame. I can change the duration, color and other things right from the function input. Very handy for debugging.

27

Very impressive work as always Smoking :slight_smile:

28

Thanks, it’s kind of a test bed for some new concepts I had for navigation and line of sight. It’s been very informative and has opened up some very useful standard approaches for procedural approaches to pathfinding and group movement, as well as post processing of pathfinding routes which will be invaluable in my other projects. I also hope to develop this RTS game more in the future if I ever get time.

29

Someone deleted my post to you?Who did that?I had posted some weapons I had wanted you to put in the game.I have only one post now.And i made more than four posts.I found it i was confused.

30

That’d be great, I’d always wanted to do a super realistic WW2 RTS - so hopefully I can use your findings in future :slight_smile:

31

Hi, I think you meant the other thread right?

32

Yes that is right.

33

For time to time I’ll return to this thread, as this is where all my RTS experiments are collected.

The other day I was working with some particles and fund that with a little rewriting the system I was using could be used for pathfinding lots and lots of units with minimal overhead.

The downside is that it’s not all that reliable. Sometimes they walk through buildings. It also needs some optimization, but I think you can already see where it’s going.

video still processing as of this posting time. Wait a little if it doesn’t play at first. Or come back later. :slight_smile:

ducklings.blend (504 KB)
And here’s the blend file. With blender 2.73a

34

Very nice work, you may be interested in having a look at this alternate path finding method

35

Hi, thanks, that’s actually something I looked at before in another setting. It’s perfect for roguelikes, (*) 1st person shooters or any other game where you have a lot of enemies and just a single player… It’s rather expensive in terms of computing time if you have a lot of destinations though.

It made me think about it though… if there are just a few controllable infantry groups (like 5-6 per team) with quite a lot of infantry in each one, then this method could work quite well especially if you’re using quite a course grid of nodes.

****as attested by this article on roguebasin, with a little tweaking of the numbers you can also make enemies flee from the player too.

36

it looks so cute!

37

I spent a little more time on the infantry concept today.
It’s just a few days until my wife gives birth, so I can’t work on any project seriously, but I had a couple of hours to work on this old project today. I’m getting closer to the overall goal of a simple working RTS game.

I used replaceMesh() for the animations.

38

what about only replacing meshes of units on screen?

are the actors 3d or sprites?

39

They are sprites, right now just one kind but there would be multiple types of characters.

I’ve set up movement to be separate from visualization so I can turn most of it off when they are off screen. Also enemy squad members will only be spawned when they are near to being spotted. Before that they move as a single object.

40

Will you make a great RTS game from this?