RTS game tools experiements.

Game Engine Works in Progress and Game Demos
1

What does it take to make a real time strategy game?

I’m going to be posting some demos for various necessary functions for a real time strategy game. If you have any of your own that you’d like to share please post them here.

Firstly I’ve been working on movement orders and unit management along with fog-of-war.

Here’s a little demo:

And a blend file if you’d like to take a look at the (rather messy right now) implementation:
fog-of-war-demo-2

And here’s an old left click selection box script, again, pretty messy, I’m sure it could be cleaned up, but a good starting point:

selection_box.jpg791×460 54.3 KB

I’ll probably be using these to move forward with some other ideas to make a fairly simple RTS, so expect a few more tools later.

This is my usual way of working on a new project, to put together a few basic demo files to see if I can make some game mechanics work, then I set about trying to integrate them together. It’s not the most organized of workflows, but it sure beats doing loads of planning only to find something I wanted to do was impossible.

2

I spent a little time making a demo which uses multiple agents, but it’s difficult to get it right.

Rather than:

for agent in agent_list:
    for vertex in mesh:

I think it’s going to require:

for vertex in mesh:
    for agent in agent_list:

otherwise each new agent checked will overwrite the previous pass, blacking out the other agent’s seen vertices.

Working with meshes and setting vert colors can be quite slow, so I want the operation to be as quick as possible. The good thing about verts is you can store them in a list or dictionary as references and perform operations on them outside the main loop.

This method opens another option, so I’m trying out a white_list and black_list so that I can add all the verts in to the list and then only darken the verts which are not in the white list. or a single list or dictionary of all applicable verts in a tuple along with a boolean as to whether they should be white or not.

EDIT:
Well, it works after a fashion. However, it takes a lot of processing once you get a few agents in play.
I can probably reduce the drain by reducing the vertex density of the meshes…

3

Id like to ask a question about the fog of war part. It does get pretty resource intensive as i imagine, but my question is “why”? Warcraft I and 2, and also the original command an conquer game uses a fog of war. Those games were made to run on a 486/80MHZ(yes MEGAhertz), with 8 megabytes(yes megabytes of RAM) and did not seem to get bogged down by the fog of war.

  1. Do you think its because all of the other elements of the game were also within a such a low resolution that the FOW was a non factor.
  2. Do you think that they used and implementation of the fog of war that we have not discovered to use yet?
  3. Those game used sprites instead of 3d models, Do you think that they basic in game resources were so low that the FOW was such a non-issue that it could be programed ‘however worked’ without hurting performance.

I agree the the BGE’s performance on things has to be tweaked to keep any project up on par and running smoothly. But if these games that are over 20 years old(I think even Dune used FOW) on such low performance machines and had no performance issues on FOW, how is it that we are dealing with performance issues on FOW with our machines being so much more powerful . Ive never tried anything with FOW im just curious as of how, after 20 years and over 100X of procesing power and ram amount, we still have problems getting something to work smoothly that they could do 20 years ago. Is it our implementation?, or is it because we are consuming resources on all of the other things. How did those games handle FOW. Is it something we can duplicate, or do wi have to do it totally different as a result of us using a 3d environment.

Just wondering your thoughts on it. Becuase even if BGE is a little underpowered. It should be able to hable anything my 1991 computer could

4

EDIT:
The biggest drain is in setting the vertex colors, but there are ways to reduce the time taken to calculate the viewable area. See the next post for a practical implementation.

5

I focused again on the fog of war script, I removed all the movement and other stuff so I could get a more accurate understanding of what was causing slow downs.

upload.jpg756×521 91 KB

I think I’ve got something a little bit more focused and stripped down now, it clocks in at 0.29-0.36 ms logic once every 60 tics which means it won’t put a dent in the 60 frames per second I’m aiming for in the project. In fact I can have it running at zero tic intervals and still clock 60 frames per second. This is even with 16 agents in the scene.

I got this improvement in performance by avoiding unnecessary checks.
But rather than using lists and checking if a vertex is already in a list as I originally intended, I used a property:

see = False

and then looped through the players to see if any of them could see the vertex. If someone can see it I set “see” to True and stop checking for the other players/agents. If see == True at the end of the loop I color the vertex white. Otherwise it goes black.

After some thorough testing of different approaches to the problem I can say:

When making checks, stacked loops like [[for vertex in mesh] for player in scene] can really multiply pretty quickly. They can cause performance problems. It’s important to get out of the loop, or at least stop making checks once you have the data you need. once see == True, there’s no need to continue checking.

Likewise, “if vertex in seen list” can cause problems one the seen list gets above a few hundred entries. It’s better to perform your transformations or alterations inside the main loop rather than creating a list of targets for your operations. On the other hand, a short check of whether something needs to be checked at all (the view_sphere list builder is a good example) can save a lot of performance drain later.

Using ob.getDistanceTo(point) is preferable to writing your own distance checking function. Even though my own function was only checking 2d distance rather than 3d, and my script used simple manhattan distance rather than a more complex calculation, the blender function getDistanceTo is a compiled function, and runs much faster. Nearly 3 times faster in fact. I just wish getDistanceTo could be performed on two points, rather than one object and a point, I could improve my A* script a lot with it.

I’ll be looking at some more RTS tools soon, if you have some particular function of a traditional RTS you’d like to see worked on, please make a request here.

Some things I’ll be tackling:
infantry sprites
infantry squads and formations
A* navigation speed ups
avoiding traffic jams by pathfinding units
loading infantry in to vehicles or buildings and unloading them
objectives and victory condition checks

Hopefully each experiment will result in a usable template that others can take to use in their own projects.

I’ll also be trying to learn how to tidy up my python scripts a bit while working on these functions.

EDIT:

I did some experiments with shadow casting.

Unfortunately, not only does it not look good (there are gaps in the shadows) it also takes a massive performance hit.

I’m going to try doing something with shadow paths based on linear extrapolation, hopefully I can get it to work, otherwise we don’t have the ability to block vision with buildings. I remember old games often didn’t have that function, but I’ve seen it working in newer games, so it should be possible.

6

I made a lot of progress with the script today because of what I learned from the early tests; It’s better to use a built in function that to try to write one from scratch. So I decided to use the rayCastTo function to test for object which block fog of war.

upload.jpg1030×666 162 KB

You can see it working with large object and small ones. All the white round objects are agents who are checking for fog of war. All the big white squares are buildings. The small lack circles are trees or whatever.

It works much better and there is no real reduction in speed from without it. However, it is currently making the buildings unseen as well so I’ll have to have a think about that. It’s probably going to involve just using a view blocking object which is a bit smaller than the building.

I’m going to take another look at the game which I’ve been drawing inspiration from and decide how they handled it.

7

Please excuse me if these ideas are noobish, I have not tried working with Fog Of War before, but have some ideas for various things.

Can you cut processing by saying: These points are a long way away, and do not need to be checked for the next x frames, these points are closer so I’ll check them more often. This will also help stagger the load.
Example: Blocks within and 5 units out in all directions from where the player can see are checked every frame, blocks from 5 units to 15 units are checked every 15 frames, blocks further than 15 units out are checked every 60. Assuming a player can’t move more than a few blocks per frame.

To solve the buildings not being seen because they’re blocking the view, can you perform a check for, instead of the normal facing the agent, a backface? That way you can see everywhere in the building, but not out the back.

8

I just had a look at the back face idea but it doesn’t seem that Blender’s raycasting can work that way. It seems like something that should work, but didn’t. Thanks for the suggestion anyway. :slight_smile:

However it did lead me to try using cylinder type bounds which worked better. For the actual detection of the building object I’ll be using a different script which will check to make sure to avoid self collisions (if hit_object != target) but with the mesh based fog of war the ray emitter is the agent and the ray target is the location of the vert, so there’s no chance to check for self collision without adding an extra section to the main loop (which means more performance drain).

The script does work similar to how you suggested, first I check each chunk of 10x10 vert ground and see if it’s near enough to bother checking. If it is, it gets processed, if not it gets left alone. Processing then goes on to check the 10x10 section of ground (@ 100 verts to check against each player) but each vert only gets checked until it can be flagged as visible. After that there’s no need to check further.

As the agents are all going to be slow moving it doesn’t really require a fast update speed.
About the only thing I can think that will increase speed at this point is doing an in fulstrum check so that only tiles which are in view of the camera get checked. Maybe there I could do something like you suggested so that tiles which suddenly come in to the main view area get processed outside the normal loop, but still overall the normal loop only checks tiles every 30 tics or so.

I think I’m happy with it so far, it does what I wanted to do.

9

I’ve done some more work and I’ll call this phase of the project finished.

I’ve changed

see = True

to

see = 1.0

or

see = 0.5

So there are two levels of reveal. Now the core viewing area of each unit is fully visible. Any enemy units in this area have a high chance of being spotted even if they are concealed. The outer area and any area obscured by buildings or trees will be 50 visible,enemy units have a good chance of not being seen here, though you can see the map enough so that you can navigate, or target probable enemy locations with artillery.

Here’s a video:

The yellow dots represent tanks, the green one is an infantry squad. The each have different viewing distances.

I hope the end result is going to be kind of claustrophobic. WWII era tanks are great but they need infantry or scout vehicles to act as their eyes and ears. If you go in with only tanks you’re going to get cut to pieces before you even see the enemy. And using tanks in a city is just plain bad.

And here’s the Blend file from the video:

10

Moving on with other experiments I’ve been working on vehicle movement, especially trying to work out a good way of towing trailers and other vehicles. I think I’ve got it sorted out for now, though there’s some work to do on movement and also on pathfinding. I’ve got some great ideas there though which should make for fast and fairly intelligent pathfinding.

Here’s a video of the basic movement:

11

Another experiment today, cam movement controlled by mouse.

When you make a game as complex as an RTS it’s good to follow existing conventions, or even replicate control methods you’ve seen in your favorite games. Someone coming to your game for the first time shouldn’t find it too difficult to work out how to play. It’s also good if you can avoid too many essential hard coded keyboard shortcuts, with most controls accessible from the mouse and screen icons. I’ll be adding some keyboard shortcuts, but they’ll be optional, for advanced players. :slight_smile:

I’m going to be using the cam movement system which has been used in several games where you move the camera by moving the mouse pointer close to the edge of the screen. I’m going to be adding rotational movement by holding shift and moving the mouse from left to right.

You can try it out here:
Camera movement script

It uses an always sensor and a “shift” keyboard sensor. I can be changed to use a mouse movement sensor if you like, but I’m going to be calling it as a function during the main game loop so it’s on always for now.

It feels a bit jerky right now, I’m not sure what’s causing that. I’ll take a look to see if I can work it out, but for now I’ll be moving on to the more complex aspects of navigation, I want to get straight like movement working with multiple units selected first, then I’ll be integrating a basic pathfinding script, again using formational movement.

I’m also going to be rewriting the selection box code to use screen positions rather than ground position, I’ve learned a few tricks since then which makes it much easier, no need for an empty to be manually aimed at the screen, I can just use a vector.

12

A big update to movement today. :slight_smile:

I’ve implemented a lot in this demo, selection, camera movement, formations and bezier paths are all included.

Lots still to work on but it’s coming along slowly. I’d be grateful if people could try it out and tell me if it has any bugs or if it runs slowly on your system. I’m getting a solid 60 frames per second even with large groups of agents. I don’t know how that’ll work out once I start adding A* navigation, but it shouldn’t be too much slower, I’m trying to design the game to avoid complex maze like levels.

You can download it here:
navigation7.blend (910 KB)

CONTROLS:
Left mouse button to select. (click or drag a selection box)
Right mouse to order agents to move to location.
Move the mouse pointer to the edge of the screen to scroll the camera.
Hold shift to rotate the camera.

I’ll be changing the controls somewhat, any suggestions?

13

The frame rate is great on the dell i am using.

14

i like the movement and its very smooth. If I had to debate something it would be the following. I noticed that the mouse can go “off-screen” and still move the world that way. The direction is correct, but if I remember in the old games the scrolling would stop if the mouse went outside the window (keeping the “game” pointer inside of the game window). I assume its this way because your using mouse coordinates to move your screen. Ive seen it done this other way in the past. Have you thought about putting invisible “borders” on the edges of your screen and if the mouse is over them it scrolls the appropiate way. Here is a crude example. When the mouse was over the appropiate border it would scroll that way. Im not sure if theres a benefit over one way or the other, other than maybe you could keep the game mouse in the Screen. Just curious on your thoughts. (But thats how we used to do mouselooks with logic only) :smiley:

camera_pan.jpg1280×720 63.4 KB

Edit: After Looking again at your file im very curious as to how you did your box select. Goran has a tutorial on box select and I just generally assumed you used a method similar to his. but after looking I can see that its not the same. Are you just drawing a box and getting screen position of everything and checking if it inside the box. If so, its very smooth for doing a check as you draw the box. I assume its this part


if selection_box_size < 0.03:
        click_select = True
    else:
        click_select = False
    
    cancel_selection = True
                                                      
    for agent in agent_list:
        selected = False
        
        if cam.pointInsideFrustum(agent.worldPosition): 
            screen_location = cam.getScreenPosition(agent)
            
            if click_select:
                distance = abs(start[0] - screen_location[0]) + abs(start[1] - screen_location[1])
                                
                if distance < 0.02:
                    selected = True   
                    cancel_selection = False    
            else:
                if screen_location[0] > x_limit[0] and screen_location[0] < x_limit[1]:
                    if screen_location[1] > y_limit[0] and screen_location[1] < y_limit[1]:
                        selected = True
                        cancel_selection = False
15

I’ve found a nice set of functions in mathutils.geometry

After a bit of messing around I’ve made a function to get which points are inside a quad and add them to a dictionary for creating a graph for A*. This way I can add some empties to a building or clump of trees and automatically add that feature to the level’s walk dictionary. When I create a graph for A* I just have to check to see if any of the points are in the walk dictionary and are therefore unwalkable.

building_check.jpg738×630 184 KB

I can also do the same thing with rough terrain or water for adding difficult or slow terrain, though I may just use a larger grid of terrain types and then use rounding to see where a point is in that grid. For large or complex features I can use multiple convex quads.

These points can also give me some “walls” or vectors which can be checked for line intersection for some simple 2d collision detection to see whether A* is needed when moving or not.

EDIT:
I may try doing the same thing with a mesh, there’s a similar function which gets if a point is within a triangle, I can iterate through the polys of a mesh and get their vertex positions, then offset them by the object.worldPosition… It’d be much better because I can use more complex shapes and it doesn’t matter if they are convex or not.

EDIT2:
Ah yes, that’s better.

building_check2.jpg607×536 102 KB

I’ll be keeping that one in mind for my other project. An excellent way of generating a walk (or nowalk) mesh for level arrays. It was pretty quick, but I don’t think I could use it for real time collision checks. I’ll just use it to generate a walk dictionary which can then be checked for collisions by rounding.

EDIT3:
Thinking about it, maybe it can be used for real time collision. If I store the triangles (or quads, I wrote an adaptation for that) in a dictionary, then I can use the checker on that, rather than pregenerating all the points. This is going to take some serious testing to find out the quickest way to do it.

EDIT4:
One way I have of stress testing a function is to call it many times in a loop:

for _ in range(250):
    run_function()

This shows me how the frame rate will be impacted if there are many agents calling the function at once.
Testing reveals that using check to test for an intersecting line between the points of the triangles is the quickest way to check if A* is needed. It’s very fast, even when stress tested.


The really good thing about using real time data instead of the pregenerated list of points is that I can change the spacing in any A* check. When you’re far away from the destination, a spacing of 3 is enough to avoid hitting any buildings, while when you’re close to the destination we can be more granular, maybe even as close as 0.5 blender units. Or I can use a widely spaced check to find an overall route and then use a granular check for getting to the next point on the overall route. I may need to write something special to cover rivers and bridges but I can see that this would allow for very fast pathfinding even with many agents. I think I may do some kind of landmass type data map, with bridge locations to improve river handling. I’ll have to see how it works out.

16

I’ve got to decide about how the levels are going to be laid out before moving on to the next part. I want rivers to play a rather major part in level design, they were a key element of the battles of WW2 so having a game with no rivers wouldn’t be smart.

I think I’m going to design the levels around a 4x4 or 2x2 block of river areas. Either a a block has a river or it doesn’t. From that I can judge how those sections fit together using a binary check of the neighbors. Something like this:

river.jpg512×512 31.9 KB

The first tile above is 0000 meaning that the tile has a river, but none of the neighbors do. The second tile is 1000 meaning the tile to the west also has a river… the 16th tile is 1111 meaning all adjacent tiles have river == True.

Around that I can generate random terrain, such as hills or forests or swamps and add settlements like villages to tiles without a river. I could also have an alternative set of river variants where there is a settlement on the river.

Now it’s important to line up the rivers and potential bridges correctly because for long range pathfinding I want the low res path to go right over the bridge. If it doesn’t, agents will have trouble crossing rivers.

Right now I’m still testing whether it makes sense to have a high res walk dictionary as well as a low res one. Most agents are going to move really slowly, so they should be calculating a long low res path to a distant goal and a short high res path to the next step in the low res path.

Here’s a visualization of what I mean;

upload.jpg1024×340 230 KB

I really want to have more than just passable and unpassable terrain though. I’d like to allow movement through difficult terrain such as shallow rivers or swamps, but have a chance of getting stuck or damaged. That means generating separate data, one dictionary for pass-ability and another for move cost. I don’t want the AI to run straight through difficult terrain unthinkingly, so I’d like for it to have an effect on pathfinding too. I also need for infantry to be able to occupy houses and other buildings. That means they need some special code in order to go in to what would otherwise be impassable terrain.

Needs more testing.

One thing I’m still thinking about is using an irregular nav grid which can give the appearance of a higher res grid because of it’s irregular nature. I could use mathutils.noise.voronoi to generate the cells and add further nodes at bridges or building doors…

17

Well, voronoi didn’t work that well, but creating an irregular grid seems to be something that can have a good effect on long distance pathfinding.

The game is going to be procedurally generated so I can’t hand place the nav points like I have here, but placing some around the features which will be randomly added should give good coverage. For example, one would be placed at either end of a bridge and one in the middle to make sure.

When all nav points have been added a script checks if they can reach any neighbors, and adds that neightbor (along with the neighbor’s distance- important information for A*) to a dictionary. I tried just doing that at first (V1), but it ended up with too many connections (20-30+ in some cases), which means slower processing. I tried limiting the number of connections by a simple counter, but that meant missing some important near nodes(V2). So I finally added all connections, then sorted then by distance, then culled them to a max number (V3). I may add a further refinement to never cull connections to important places such as building entrances and bridges. This is the important thing about this method, it can cover a lot of area but still find important connections without fail.

nav_points.jpg512×1603 763 KB

Again it’s going to take some work to modify the A* script I’ve got (which works with grids) to work with arbitrary points and distances.
I hope I can get it working. :slight_smile:

18

a_star_found.jpg713×464 40.2 KB

Yay! working a star with waypoints and mesh based obstacles.
Time for bed. :slight_smile:

Once I’ve got it working completely I’ll post it in the resources section. It’s going to take some polishing, but I can’t think of an easier system to use for dynamic pathfinding (can work with randomly generated levels, doesn’t need multiple walk meshes, should be fairly speedy when it’s done).

19

Nice work !

20

Thanks, I’ll be trying to put it all together soon with fully 3d terrain and movement, as well as cleaning up a few issues (like accidentally giving orders which send units outside the play area).

Later I’ve got to work on:
River design and placement.

  • “Slow” terrain such as river fords and swamps.
  • Random generation of terrain.
  • Random generation of settlements and bases.
  • Infantry formations and movement.
  • Infantry occupation of buildings.

And other stuff, before getting to work on combat and all aspects of that.

I may introduce some of the combat early, just to see how it works out with the kind of map size and visibility ranges I’m working with.

Before moving on to combat.