Tuesday, 6 December 2016

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

Saturday, 3 December 2016


The infantry are coming! You can see a quick video here.

Infantry are moving around as expected, it's easy to select them and get them to go where you want. As of yesterday there were still problems with them getting too near to tanks, and not knowing to get out of the way when a vehicle wants to come through. I think I got that covered today though.

Here's a first version, you can see something is up right away though if you look carefully. That's right, I forgot the camera is rotated 45 degrees for an isometric style view so the infantry are facing the wrong way when moving. After adding a 45 degree offset to the code for sprite display I got them to face the right way.

I also tweaked the code to stop them from walking through each other. Now they won't occupy the same square as a fellow squad member. They also adjust their avoidance radius based on their state. If they are standing still they will move out of the way sooner. But while walking they are not so quick to give way to vehicles. If they are given the order to mount a vehicle, they will reduce the avoidance radius to 0, effectively allowing them to go right up the vehicle and get on board.

One thing I'm considering is the possibility of giving tankers the order to ignore friendly infantry when driving. This would leave it up to the player to keep their infantry safe from being run over by their own tanks. I don't really like the idea because war is violent enough without making it possible to intentionally run over your own guys.

Another consideration is whether to give vehicles code to manage right of way. Vehicles which are already moving would have a higher ROW index, vehicles which move later would avoid them the same way infantry do. Perhaps smaller vehicles or non-combat vehicles could also be asked to always give way to tanks... It's a really nice idea, but I think the result might be even more traffic jams. As I've said before, make the AI too smart and the player will be disappointed if they don't perform well in battle. Make them dumb and the player will be more inclined to take the responsibility themselves (and maybe not get annoyed at the game's AI).

Wednesday, 16 November 2016

Infantry experiements.

Vehicles are working nicely now, and I think the vehicular game-play is coming to a point where I'm pretty happy with it. You can see some of the more recent progress here.

Now with tanks churning their way through the mud, I think it's time to start bringing in the PBIs.

Poor Bloody Infantry.

I need to see how infantry reacts to vehicles, how well (or badly) my pathfinding routine works with large numbers of agents and vehicles. And overall how infantry works out in the game. I think the plan I have is going to work quite well. Infantry move very slowly, so the pathfinding calculations shouldn't happen very often. The pathfinding itself is very rudimentary, just like that I'm using for the vehicles at the moment so the overhead should be small.

I've actually got a whole load of infantry building scripts and models left over from an earlier version of the game, but I'd like to start from scratch on that one really. I'm experimenting with quick hand drawn textures and low poly models, so far it doesn't look too bad. Remember, the infantry sprites are going to be tiny on screen...

Right now I'm considering if it's worth the extra time to paint these guys up using a more complex texture painting technique, the final result is so small I don't know if you'd really see any benefits. Maybe tomorrow I'll post a side by side comparison. For now I'll probably use some of my old assets, I've got two different riflemen sprites:

And you can see what they look like walking around in this video.

Monday, 7 November 2016

General Principles for Reducing Logic Overhead (Part 2)

In my post yesterday I forgot to mention a few things which would be even more helpful when trying to make your game run smoother on low end machines.

Firstly I forgot to mention states.

Probably the biggest improvement you can make to your code if you're not already using them is to add behavior states.

When your agents are doing an action, that action should be a separate state. They should concentrate only on that state, all other calculation should be avoided.

Sunday, 6 November 2016

General Principles for Reducing Logic Overhead.

Today I was reading Blender Artist's Game Engine Forum when I came across a post about very high logic overheads. Of course slow game performance is a real problem with a lot of indie games, and low frame rate can easily be enough to turn someone off your game before they even really get started. It's an important issue for indie game-devs and hobbyists alike.

[LAG=game over]
So I decided to write a blog post about it.

First of all I should point out there are lots of areas of overhead in a game. One area that often causes lag is graphics, a game engine like Blender is still using quite old methods of rendering and lighting so you can't expect too much from it. There are easy ways to reduce rasterizer overhead which I think I've talked about before many times over at Blender Artists.

The problem the BA poster was having though was specifically with Logic, i.e python scripting and the Game engine logic bricks.

With games developed by hobbyists it's common to find code which is not well optimized or not well planned. Often tasks are repeated even though they are not needed, or bottlenecks occur which can cause lag spikes.

[All the AI characters trying to change a lightbulb at the same time]

Lag can be manageable, but severe spikes can be a problem. There are 1000 milliseconds in a second, and the Blender game engine runs 60 frames of logic every second. That's 16.666ms every frame. If a frame takes more than that to calculate you start losing frames. 

My first finished game sometimes spiked up to 20ms logic which meant a lot of lost frames.
[Why is this my most popular game?]
I couldn't do anything now to improve that though, it's an old game and I didn't know much about project management so I made a lot of mistakes. I couldn't just go back and fix them, since it would mean a 99% re-write of the code.

As time's gone by I've found ways to improve the logic overhead on my games, nowadays I expect about 2-4ms for a finished game, and during development I usually see less than 1ms. I got to this point by adopting a number of design principles which help me to keep calculations to a minimum.

Here are a few of the principles I try to stick to:

[Can you even tell how many frames per second?]
1. I Don't do AI calculations every logic tic.
Most of my games are tile based, so moving from one tile to another is a single action. That one action takes about 0.5 to 2.0 seconds. Some events can interrupt that action (like the actor dying) but for the most part the actor only needs to calculate behavior once every action, instead of 60 times per second. Many older games were turn based and tile based, I remember sometimes waiting up to 15 minutes for a turn to finish and the AI to do all its calculations. You don't have to go this far, but having a scheduler or set duration actions is better than just continuous calculation. Most humans can't notice a half second delay in an AI's reactions.

[What's happening off screen? Who cares?]

2. I Don't calculate things off screen.
If an enemy is off screen you don't have to do anything with it. Put it to sleep until it gets close enough to interact with the player. Better yet, only spawn enemies when the player gets near. If you're using a sprite animation, you don't need to update it when the agent is off screen, only when you can see the enemy. You can use frustum culling or ray casting to check if an agent is off screen.

[for agent in agent_list:]

3. I Work with lists of different kinds of entities and manage them in different but standardized ways.
Each of my projects has a main loop which shepherds all the different aspects of the game. Lots of calculations are done centrally in the main loop so they don't have to be repeated for each element further down the line. It should be easy to get a reference to the nearest enemy, or the distance to the player from any enemy without doing the calculation again for every single entity. Agents, particles, lights etc... each have their own sub process. Particles don't need to do agent things and agents don't need to do particle things. I keep types of things separate.

[How can you make a game without A*, is it even possible?]
4. There are other, ways of doing things which are not the latest or the best but they are better for performance, it pays to research old games.
Most modern games use a variant of A* for AI navigation. If you're using the nav meshes in Blender you're using something similar. But in Python this can be slow, cause massive Lag spikes or require multi-threading to manage the overhead required. I found an old "dumb" AI trick that only checks the tiles surrounding the agent to see which is nearest the target and then keeps a list of those already visited while moving only clearing the list if it can't go any further. The result is much, much faster than even the most optimized version of A* in python and gives a result that can be described as "good enough". Most players won't know the difference, but it allows dozens of agents in the game at the same time with almost no overhead. (here's a video of an old project with around 100 enemies running at about 4ms, notice that when only the player is in the screen Logic is at around 0ms!). It's also easily adapted to allow fleeing or patrolling behavior. Knowing how programmers did something when they only had 128k of ram can help us to find ways to reduce overheads in our own games to a level that approaches zero. (Here's an excellent article on the AI of Pacman for starters).

[bullet time, collision sensor=True]

5. I consider multiple ways of doing something and decide which is likely to have the lowest overhead.
An example is bullets. One way to do things is to have a collision sensor on the bullet and detect when it hits an enemy. Another is to have a collision sensor on the enemies and detect when a bullet hits them. If there are 7 enemies but 700 bullets on screen it's easy to guess which way will save the most calculations. Sometimes this requires a bit of lateral thinking to fix holes in the design, in this case the level also needs collision sensors for when bullets hit walls.

[You've got mail!]

6. I (often) use messages and callbacks rather than continuous polling.
Rather than making any calculations or changes to the main scene, my UI scene just records button presses or mouse movements and turns them in to messages. If I click the menu button it sends a message "menu_clicked" to the main controller in the main scene and the calculations are done there. My UI is therefore mostly inactive, just waiting to receive input or return messages from the main controller. My agents receive messages from the main controller too, instead of checking every frame to see if one of a dozen things have happened (keys pressed? mouse moved? buttons clicked? object collided?) they just check to see if they have received a message. If they have, then they have to parse the message and act accordingly, but if not they get to sit back and do noting (or continue doing their current action). I have to admit though this is one area where I'm still trying to develop. It's often easier and safer to just poll something rather than trust that nothing changed since the last message was received.

These are design decisions not a roadmap, not all of them will be useful for every type of game, but if you're having trouble with Logic spikes they might be helpful. The point is to try different ways of doing things and see which has the best result for you.
There's no silver bullet for fixing the problem of working with a slow scripting language like Python, you just have to take care to work within the limits that imposes on you. There's no point blaming the game engine or the Language for not being fast enough, without good project management and planning it's unlikely that moving to a faster language or a better game engine would result in a better, smoother running game.

Saturday, 5 November 2016

Procedural terrain for Real Time Strategy.

The current phase of development is taking longer than I'd like because of the difficulty of designing procedural terrain for Real Time Strategy games.

In many RTS games water is impassable, this makes bridges very important strategic locations. But the flip side of this is that units that can go through or over water become valuable too.

Unfortunately it's not so easy to just let any unit become amphibious. If a unit can go through water it needs different pathfinding, it also needs to know the difference between moving in to water from the shore, and moving in to water from a bridge. Most RTS games are not true 3D. So bridges, though they look like they are raised up above the surface of the water are usually not. Driving your tank over the side of the bridge and in to the water would give some funky results.

So I need to mark tiles as water, but also mark bridge tiles. An option would be to add impassible tiles along the edges of the bridge, so you just can't drive off or on to them. Another option would be to hard code amphibious units not to go from bridge to water or vice versa.

Another problem is to keep the nice flowing appearance of rivers while making them modular. I want them to curve but that means either writing a lot of heavy code (which will get executed when you start, lagging the game start up more than I'd like) to curve them by hand, or cutting them in to sections and treating them just like terrain tiles.

The same issue is attached to roads if I want to handle them as objects instead of just different textured terrain, though there's the problem of making them intersect...

Other problems include placing and keeping track of walls, buildings and such. Also code for more types of terrain such as fields and woodlands.

Thursday, 27 October 2016

Vinland 1936

What have I been up to this month?

Well you can see it in a couple of development blog videos, here, here and here.

Vinland 1936 is a game I've been working on (on and off) for about 3 years. It is somewhat based on the old Nirval interactive game, Blitzkrieg;

I hope you've played it since it is one of the best games ever!!! (IMHO)
Blitzkrieg was a real time tactics game. You didn't build a base, or spawn units. It wasn't about rushing the enemy. You got a small number of troops and vehicles that could be replenished or repaired if you had access to a supply base and the right supply trucks, but couldn't be replaced if lost. Once your vehicles were destroyed and your infantry killed you were finished. You couldn't just churn out some more from your factory and have another go at rushing the enemy guns. This made you invest a lot in each of your units. They really mattered.

It was also procedurally generated. Each mission (except for the historical missions) was put together from a sophisticated random generator. Each time you played you'd have to work hard to crack a new set of environmental puzzles. This means I can still play the game and enjoy it years later.

My own game is going to be similar, but I want to take the idea of replayability even further. In Vinland 1936 you are going to be playing an alternative history setting. Although there are a list of "historical" vehicle designs for each faction you're going to be able to customize them and create new machines. You'll not be stuck with the same old Panzer IV or Matilda II every time, your gameplay will change with the availability of rare parts, salvaged enemy chassis and your understanding of the customization program.

Here you can see an early war tank:

Slow but well armored, it has a heavy gun in the hull and a small turret.
There are several ways you could customize this design, adding more armor at the expensive of speed, adding a commander's cupola to the turret to help with visual range and targeting. Improved suspension will become available, or better weapons. Eventually you'll want to buy a new design since the small turret limits its usefulness in later encounters. But as you use it the crew will gain experience, maybe getting some special skills. It might be better to keep upgrading it rather than get a new tank with raw crew members.

Here's where having vehicle customization really makes a difference vs just having static designs. There's going to be an element of strategy in the vehicles you choose to design that will make every mission feel unique.

I really love the Blitzkrieg games, but the WWII period is so well known now it's hard for it to hold any surprises. And the most recent blitzkrieg (3) looks pretty boring to me, with very little of what made the original game so great.

I'll leave you with a picture of some of the vehicles I designed so far while messing with the vehicle editor: