Unfortunately my laptop died last night (well it boots OK but the screen doesn't work and it won't drive an external monitor) so development has ground to a bit of a halt.
I managed to get my files off by remote logging in from another computer and copying them across. I wouldn't have been completely screwed anyway as I keep all my code on an external SVN server.
Now to start shopping for a replacement...
Monday, September 15, 2008
Thursday, August 28, 2008
Collision detection systems for RTS games
From observing the unit movement behavior of several real time strategy games it becomes apparent that there are two major collision detection systems, each with their own pros and cons.
Tile based collision detection system
With this system each unit sits in a discrete tile on the tilemap. Only one unit can occupy a tile at any one time. As a unit moves around the map, it moves from one tile to another. Before moving into the next tile, it checks to see if any other units already occupy this tile. If the tile is occupied, the unit recalculates its path, if not then it moves into the tile.
There are some great advantages to this implementation:
1) It is extremely simple to implement
2) It is a very stable system (no units will ever get stuck in one another etc)
3) It has little CPU and memory cost which scale well
The main disadvantage of this method is the rigid nature of the movement of units. It is very clear of the fact that units sit in discrete tiles and there is a lack of fluidity in their movement.
As an example, here is a youtube clip of Warcraft: Orcs & Humans which uses the tile based collision detection system:
Note the fixed movement at 45 degree angles (i.e. North, North-East, East etc) is particularly rigid-looking and not really suitable for modern RTS games.
Object based collision detection system
Each unit is modeled as a sphere, and each building as a box. Standard collision detection techniques which may been seen in other genres of computer games are used. At each frame of movement for each unit, collisions are checked for, and upon collision are moved appropriately.
The clear advantage of this system is that the units move very fluidly and with a natural motion. It also makes it easier to make troops walk and fight in formation, as they are not constrained to discrete tiles.
However, it is particularly difficult to implement effectively and with low CPU cost. The main problem is that each unit must check the positions of surrounding units and buildings to test for collisions. For large groups of units, the checks become greater in number, having a heavy impact on the CPU.
Path finding/following also becomes an issue as it becomes more difficult to avoid dynamically moving obstacles. This is discussed in this article on Gamasutra.
An example of a game using object-based collision would be Empires: Dawn of the modern world. A youtube clip below shows this in action:
You can note at the beginning of the clip that as the soldiers line up to shoot at the building, the units kind of 'bounce' off each other.
The solution for Warring States
At first I implemented an object-based collision detection system purely for aesthetic reasons. However I soon noticed the problems that are discussed above, particularly with object avoidance. Units tended to get stuck when they tried to navigate around large groups and it would take a lot of work to make the system work well enough to my satisfaction.
As I want to start focusing on the AI system, I've decided to revert to a tile based collision detection system. However I'm not restricting the movements of units to grid-based movement as seen in Warcraft.
Tile based collision detection system
With this system each unit sits in a discrete tile on the tilemap. Only one unit can occupy a tile at any one time. As a unit moves around the map, it moves from one tile to another. Before moving into the next tile, it checks to see if any other units already occupy this tile. If the tile is occupied, the unit recalculates its path, if not then it moves into the tile.
There are some great advantages to this implementation:
1) It is extremely simple to implement
2) It is a very stable system (no units will ever get stuck in one another etc)
3) It has little CPU and memory cost which scale well
The main disadvantage of this method is the rigid nature of the movement of units. It is very clear of the fact that units sit in discrete tiles and there is a lack of fluidity in their movement.
As an example, here is a youtube clip of Warcraft: Orcs & Humans which uses the tile based collision detection system:
Note the fixed movement at 45 degree angles (i.e. North, North-East, East etc) is particularly rigid-looking and not really suitable for modern RTS games.
Object based collision detection system
Each unit is modeled as a sphere, and each building as a box. Standard collision detection techniques which may been seen in other genres of computer games are used. At each frame of movement for each unit, collisions are checked for, and upon collision are moved appropriately.
The clear advantage of this system is that the units move very fluidly and with a natural motion. It also makes it easier to make troops walk and fight in formation, as they are not constrained to discrete tiles.
However, it is particularly difficult to implement effectively and with low CPU cost. The main problem is that each unit must check the positions of surrounding units and buildings to test for collisions. For large groups of units, the checks become greater in number, having a heavy impact on the CPU.
Path finding/following also becomes an issue as it becomes more difficult to avoid dynamically moving obstacles. This is discussed in this article on Gamasutra.
An example of a game using object-based collision would be Empires: Dawn of the modern world. A youtube clip below shows this in action:
You can note at the beginning of the clip that as the soldiers line up to shoot at the building, the units kind of 'bounce' off each other.
The solution for Warring States
At first I implemented an object-based collision detection system purely for aesthetic reasons. However I soon noticed the problems that are discussed above, particularly with object avoidance. Units tended to get stuck when they tried to navigate around large groups and it would take a lot of work to make the system work well enough to my satisfaction.
As I want to start focusing on the AI system, I've decided to revert to a tile based collision detection system. However I'm not restricting the movements of units to grid-based movement as seen in Warcraft.
Thursday, August 14, 2008
Fog of war, building animation and gui interface
I've added a 'fog of war' effect to hide areas of the map that have not yet been explored by the player. A grey scale texture contains the data of which areas have been explored, and then this is fed into the terrain shader to darken the areas which are yet to be explored. I'm quite happy with the effect, although objects and trees tend to 'pop' in and I'd rather put a fading in effect as they become visible.
I've also modified the building animation, so a 'scaffold' model is erected first, then the building and then the scaffold descends again. This makes it easier to see where the building is being built, and the progress of its construction.
The last thing visible in this post is the GUI that I have started implementing. The selected units or building are displayed across the bottom of the screen, and their actions are available along the left side of the screen. The minimap is displayed on the bottom left side of the screen.
Below is a video to show the effects mentioned:
I've also modified the building animation, so a 'scaffold' model is erected first, then the building and then the scaffold descends again. This makes it easier to see where the building is being built, and the progress of its construction.
The last thing visible in this post is the GUI that I have started implementing. The selected units or building are displayed across the bottom of the screen, and their actions are available along the left side of the screen. The minimap is displayed on the bottom left side of the screen.
Below is a video to show the effects mentioned:
Friday, August 1, 2008
Two new youtube videos
I've uploaded two new youtube movies showing details of the game. The first shows a number of workers collecting gold and lumber and returning them back to the town center. The second video demonstrates the grass shader as it is too difficult to see in the first video due to the compression of the video.
Monday, May 5, 2008
Update on progress
It has been almost 2 months since I last made a post and a lot has progressed in this time. Below is a screenshot of the latest build:
To briefly go through the features in the screenshot:
- New unit models are featured for the worker, soldier and archer and are all fully textured
- The building model from a previous post is now in-game and fully textured
- Volumetric shadows from units and buildings
- Trees are randomly scattered on the terrain with variations in size and will flutter in the wind.
- There is a new water shader in the game, although I am not yet satisfied enough to display it in full.
Other features under the hood which you can't really see in a screenshot include:
- The first pass of networking code is in and running. Multiple computers can connect to the same game although if any network errors occur the game currently quits on all computers. I am yet to implement the team/player mechanics so everyone can effectively control everything. I haven't noticed any sync issues yet and I am also yet to try over a long distance/high latency environment.
- A database back-end system controls the various game data structures. These include information about models, shaders, textures and materials as well as statistics about various game units and buildings. It is quite trivial to add an extra game unit or building and can be done by editing the database file. This file also specifies which units can build which buildings, which buildings can train which units etc. The database is just an XML file so is easily human readable. I have used the TinyXML library to do my parsing as I needed a simple lightweight cross platform parser and this works quite well.
- The groundwork for the GUI system has been written with button widgets and event messaging systems in place. Font rendering has not yet been implemented which is why this has not progressed much so far.
- First pass for fog of war has been done but I don't like the way the fog looks so I haven't showcased this yet.
My objectives are currently set on the game logic:
- Implement the player/team structures
- Add mechanics for resource collection
- Add build mechanics
- Add training mechanics
- Add the combat system
When these are all in place the game will be playable (although in a fairly crude state) . I will then be able to move on to interface controls and general polish.
To briefly go through the features in the screenshot:
- New unit models are featured for the worker, soldier and archer and are all fully textured
- The building model from a previous post is now in-game and fully textured
- Volumetric shadows from units and buildings
- Trees are randomly scattered on the terrain with variations in size and will flutter in the wind.
- There is a new water shader in the game, although I am not yet satisfied enough to display it in full.
Other features under the hood which you can't really see in a screenshot include:
- The first pass of networking code is in and running. Multiple computers can connect to the same game although if any network errors occur the game currently quits on all computers. I am yet to implement the team/player mechanics so everyone can effectively control everything. I haven't noticed any sync issues yet and I am also yet to try over a long distance/high latency environment.
- A database back-end system controls the various game data structures. These include information about models, shaders, textures and materials as well as statistics about various game units and buildings. It is quite trivial to add an extra game unit or building and can be done by editing the database file. This file also specifies which units can build which buildings, which buildings can train which units etc. The database is just an XML file so is easily human readable. I have used the TinyXML library to do my parsing as I needed a simple lightweight cross platform parser and this works quite well.
- The groundwork for the GUI system has been written with button widgets and event messaging systems in place. Font rendering has not yet been implemented which is why this has not progressed much so far.
- First pass for fog of war has been done but I don't like the way the fog looks so I haven't showcased this yet.
My objectives are currently set on the game logic:
- Implement the player/team structures
- Add mechanics for resource collection
- Add build mechanics
- Add training mechanics
- Add the combat system
When these are all in place the game will be playable (although in a fairly crude state) . I will then be able to move on to interface controls and general polish.
Saturday, March 15, 2008
Technology tree
I created a technology tree diagram for the game's different entities and how they interact with each other.
Green: Building
Purple: Unit
Yellow: Technology
Oriental style building
This is an oriental style building I threw together in 3ds max one evening. It has the general shape and just needs texturing and and a bit of tweaking before I put it in the game.
There has been progress on the game logic and I've put together an A-Star pathfinder which balances searches across frames. However at the moment it seems that it grinds to a halt when searching for an impossible path so it may require a bit of tweaking.
Animation is now in game and uses vertex programs to linearly interpolate vertices between frames. This type of animation isn't as effective as skeletal animation but its cheap and quick and when the characters are quite small you won't notice the difference between implementations.
I'm now working on collision detection and updating the collision grid. Currently units will not update the collision grid and will only plot paths around static obstacles. Next I'll be adding buildings into the game.
Subscribe to:
Posts (Atom)