Troopers - Real-time Strategy Game

[DoorKnobHandle]

Thanks, your interest in this project is much appreciated!

TECHNICAL ESSAY #2: Pathfinding

This is the only problem I'm having right now, although I can calm you down by saying that it's not that bad - I have it working in an at least playable state right now already and I might be able to (it's gonna be hard though) solve this after all.
      Okay, so I have units and I can move them, but they won't move smartly. If I have one or more units in location A and want them to move to location B - where A and B are separated by a body of water or a steep slope or maybe even a building or another unit - they'll move to the edge and stop there. What they should do is what is called "pathfinding" - they should find a way around the obstacle and take that route. That's not always perfect either, as that path might lead right through an enemy army, outpost or base, but that's just how most recent real-time strategy games work.
      AGS has implemented pathfinding for characters nicely as you developers probably know, so no user has to really worry about the somewhat complicated world of A*-algorithms and the like. There are reasons, however, why I can not use these already implemented solutions: first of all the project doesn't use characters to display units (that would not be suited at all), it uses the dynamic sprites in order to theoretically display millions of them, second of all, pathfinding in real-time strategy games is different from pathfinding in adventure games.
      Let me clarify that last bit: while it's sufficient to use one algorithm in an adventure game where only very few characters are moved around simultaneously, almost all real-time strategy games use several methods (one for short distance, one that is somewhat less fine but faster for more units over longer distances, etc).
      Anyways, back to the project. Using the implemented pathfinding-routines in AGS won't be possible, if I'm not mistaken, so there are two options: implement your own or just make the user define the paths himself. The former is hard to do and will most likely slow the game down a whole lot (maybe it's worth a try if I have enough time, though - I could try to optimize this; for example when moving a lot of units, only give the first twenty units the order to move, so the game doesn't slow down as much, then give the next twenty the order one frame later etc.) and the latter is what I'm doing right now - it works, but it isn't not all that comfortable. I guess I'll see.

[DoorKnobHandle]

Little update: I have finished including shadows and air-units. This turned out really nice, actually. Take a look at this excerpt from a show-off shot:

You can see the tanks are flying at the moment...

It doesn't only look nice and adds a feel of depth, it also works very ergonomically - drawing these shadows doesn't require any new artwork or anything, the volume is created on-the-fly with a second dynamic sprite, the tint-functions and the possibility to draw images with transparency. Shadows "stack up" at the moment (when they overlap, that part of the shadow gets even darker) which is not really realistic, I think, but it actually looks nice and fine to me and flying units even throw shadows on ground units and buildings which is very important to create that sense of height and depth.

As I mentioned, it allows units to fly (well, it only shows they're flying if there's a shadow) - the units actually move up or down a bit every now and then as you might have noticed they do in games such as StarCraft to emphasize their height and how they hover.

Of course, flying units will not collide with stuff on the ground (terrain stuff such as slopes or trees and bushes) or units and buildings on the ground, however they still collide with other flying units - logically.

I will actually allow players to either turn shadows off (for slower machines, should increase performance when controlling lots of units), make them absolutely black (which will be slower than the previously mentioned option, but at least a bit faster since the game doesn't have to draw the shadows with transparency) or to have them look realistic (which is what you see in the shot above, the slowest but best looking option). Shadows aren't that expensive, though, on my somewhat dated machine (P4 ~2.5GHz, 6 years old) they don't slow down that much in comparison.

What do you think? Any other ideas for effects or functionality? Do the shadows seem good to you? Any feedback is appreciated as always.

[Nikolas]

You do know that I will make this whole thread into a PDF once you're done, right?! These notes need to be documented!

What are your thoughts on sound/music? Cause I might have an idea... (to PM ONLY!)

[R4L]

I'm so happy you've revived this! If it's anything like Starcraft or Warcraft II, I'll be hooked for a long, long time.

[DoorKnobHandle]

Little update: I have been able to get some work done on the following aspects...

• improved radar-map (see first technical essay for information) - put short, it's not as blocky as the screens anymore, it works pixel-perfect for both units and terrain and it works faster...
  
  
• improved unit-movement - through a series of rather complex algorithms, units now move better in groups and shouldn't get stuck in each other or anything, this helps a lot in-game...
  
  
• units can idle now - every now and then (semi-random interval) they'll look to the left or right a little bit (they won't make a 180° turn for example, that doesn't look good, it's fixed to a maximum degree left/right, so they only move a little - they could make several full turns if you wait long enough though)...
  
  
• units can actually die now - well, currently they just disappear - I still have to think about how to realize explosions (or similar)...
  
  
• added some variation for the desert ground-tile - it looks a lot better now, no comparison to the old look at all, you'll see the difference in the next shot; when a level is drawn in the editor, the desert ground is calculated automatically and varied randomly, still (similar to the editor in StarCraft) you can change the look of single tiles if you want to force them to be one special variation...
  
  
• money- or resource-counter (right upper corner of the screen) now dynamically counts the money; when you gain "credits" it doesn't just show the new amount instantly but blends to that number by counting through the difference - for example the player starts out with 500 "credits" for testing purposes at the moment, when the game begins, the counter starts at 0 and quickly counts up to 500 and when the player builds a tank (costing 200 right now), it doesn't instantly subtract that amount but rather count down in like two seconds.
  
  
• started developing the editor - it can create new maps, load, edit and save maps which can be loaded by the main project already, eventually this will allow me to create more complex maps with more terrain-types, objects and little doodads.
  

That's the progress so far - concerning your questions about game-play, I'm able to tell you that I probably won't be able to add a real campaign (with scripted events etc.), because that would be very hard to store in the level-files, it's probably going to boil down to combat-mode only (you choose a map and play against one or more enemies) although it's possible that a simple campaign will exist in which you battle against an increasing number of increasingly good AIs (no guaranty though).

I can't promise that it'll play like StarCraft, Dune 2, WarCraft 3 or C&C 1 or any other part of the series for various reasons (pathfinding, complexity of tech-tree, application-speed etc.) just as you won't expect a common adventure made with AGS to play and feel exactly like a great top-notch commercial adventure-game such as Monkey Island 1 or DotT, but the core-elements are there and I'll try to make the best game out of the technical features that I can.

Once I have more features to show-off I might create a trailer-movie or something. I'm thinking about that because it could show off some of the work in real-time and some effects really don't show in static pictures.

[R4L]

That's great man!

I'm happy that this is still alive and well.

[SSH]

Wintermute has an interesting pathfinder algorithm. Basically, the pathfinder tries to find a straight line path. If it is blocked, it then goes through a list of author-programmed waypoints: if there's a path from a waypoint to the destination and a path from the current position to a waypoint, then it simply does two straight lines. (It also works out the shortest path if there are multiple waypoints it could use). You can then take the algorithm further using a standard graph searching algorithm like Dijkstra's. Probably the best way is to:

1. Check if straight line path possible from A to B
2. If not, calculate the cost from A to every waypoint and B to every waypoint, in a straight line. Add these to the predfined wieghted graph of waypoints. If there is a blockage, then the cost is infinite...
3. Do a Djikstra on the graph to get the shortest route from A to B.

This would be reasonably efficient for a smallish number of waypoints, provided you can take the time to set them up on each map.

[HammerBlade]

EDIT:  At the time of writing, I failed to notice that the radar had been fixed already:

improved radar-map (see first technical essay for information) - put short, it's not as blocky as the screens anymore, it works pixel-perfect for both units and terrain and it works faster...

My bad.

ORIGINAL POST:

      Okay, so I implemented this feature. And it ran slow, which is no wonder. The radar-map is 100x100 pixel sized. Every pixel on that map has to be checked against the "real" map, that means 10000 calls to a somewhat expensive function every frame. Runs at one or two fps, way, way too slow.
     

Are you sure you need to check every pixel on the map each frame?  It sounds like it would make more sense to only have the algorithm check the pixels which are within the players visible range.  Although, the only way I can think of doing that would involve writing 10000 'if' statements under the 'repeatedly execute' event.   

Maybe something along the lines of:

Code: ags

//***--VISIBILITY TEST--***
//Tests all pixels, identified with values from 0-9999, for whether they're visible.

expensive function(int ID_pixel);  //Let's pretend this is the declaration of your "expensive function" mentioned  
                                                     //above.

int pixel = 0;              //Identifying value of the pixel being tested.
bool visible[10000];  //Has the visibility status of a pixel stored (thanks to a separate function).

while (pixel !=10000)  //Keep testing until the 9999th pixel has been tested
{
     if (visible[pixel] == true)
     {
          expensive_function(pixel);
     }
     pixel = pixel + 1;  //Test the next pixel
}
     

You'd still be stuck with 10000 calls by one loop, but at least only a handful of those calls would have to deal with the "expensive function."  I hope that wasn't insultingly useless of me to mention!   

[yarooze]

You're cool man! That's awesome! 

It is fascinated, what the AGS "adventure" engine can be used for. 

[DoorKnobHandle]

Weeh, the thread was kicked off the front-page but came back, thanks a lot for that, guys!

Anyways, here's a new screenshot, notice the variety in the desert-tiles and the shadows, also, the flying units now have fire coming out of their thrusts when they move:

@HammerBlade: the problem with your suggestion (if I'm understanding it correctly) is that the radar-map has to be updated for the whole map and not only for what the player sees. Especially when units move around that are NOT in the player's view, it should show that movement on the radar-map. If you meant something else, do not hesitate to respond and clarify, please, I'm always open for ideas and I'm sure that I'm not yet doing everything in the best and most effective way.

@SSH: that's interesting and will definitely come in very handy once I try my hand at implementing the path-finder. I'm still concerned that it will run really slow though, but, as I said, the only way of finding that out is implementing and checking. At the moment, I also have another solution: I could allow the player to manually "draw" paths that the units will follow. This is not as good as a real pathfinder, but somewhat of a compromise. I'll try all different solutions out later in development.

[Khris]

Man, that looks friggin' great!
I can only imagine the insane amount of hardcore scripting that went into this so far.

About the map: from what you've written, I gather you're doing something similar to a raytrace. (If you don't, skip over the next paragraph )

Thinking about it, I came up with this solution: draw the map while drawing the main screen. Iterate over the whole map, and while skipping visited tiles that are off the screen, draw a light pixel for ground and a dark one for obstacles.
Then iterate through the units and do just the same: paint a pixel on the map for every visible unit. The cost of that should be an additional next-to-nothing.

Thinking about it some more, I had another idea: Since the map is static, draw it using three steps:
1. draw a sprite that's generated once from the level data, showing the complete map.
2. draw the units on top by iterating through them and placing the pixels at their respective map positions
3. draw another sprite on top to add the fog of war. This sprite starts out all black, is kept in memory and updated with transparent pixels whenever the player "removes" the fog of war in the game.
If the map isn't static, you only have to update a few pixels in the original map sprite. This shouldn't happen often, so again, the cost is pretty much zero.

To improve trigonometric performance, use an array holding e.g. sin(0.01) to sin(1.57).
Then derive cos and tan. Reading a variable should be several times faster than calculating a trigonometric function.

EDIT:
I've just taken a closer look at your screenshots and realised that your tiles are 25x25 while your map uses 4x4 tiles! That's unusual but luckily doesn't invalidate the suggestions I made.

[HammerBlade]

the problem with your suggestion (if I'm understanding it correctly) is that the radar-map has to be updated for the whole map and not only for what the player sees. Especially when units move around that are NOT in the player's view, it should show that movement on the radar-map. If you meant something else, do not hesitate to respond and clarify, please, I'm always open for ideas and I'm sure that I'm not yet doing everything in the best and most effective way.

When you say "what the player sees," you're referring exclusively to the main screen and NOT the radar at all, correct?

So are you saying there's no corresponding fog of war on the radar to that which is on the screen?  If so then yeah, what I suggested doesn't make sense at all.  However, if fog of war does show up on the radar, then I still meant exactly what I suggested.  My point is that, if the player can't see that the enemy is moving about on the radar, why waste resources updating that visual radar data to begin with? 

In any case, Khris's suggestion makes a ga-jillion times more sense than mine, so I guess it's a moot point.

[DoorKnobHandle]

Since the map is static, draw it using three steps:
1. draw a sprite that's generated once from the level data, showing the complete map.
2. draw the units on top by iterating through them and placing the pixels at their respective map positions
3. draw another sprite on top to add the fog of war. This sprite starts out all black, is kept in memory and updated with transparent pixels whenever the player "removes" the fog of war in the game.
If the map isn't static, you only have to update a few pixels in the original map sprite. This shouldn't happen often, so again, the cost is pretty much zero.

That's exactly what I'm doing right now (for the latest screenshot, step 3 was commented out, that's all). The rest is already working in this way and really not a bottleneck for slow-downs anymore.

To improve trigonometric performance, use an array holding e.g. sin(0.01) to sin(1.57).
Then derive cos and tan. Reading a variable should be several times faster than calculating a trigonometric function.

Luckily, I get around without using trig-functions. What I'm doing is more like look-up tables than raytracing.

I've just taken a closer look at your screenshots and realised that your tiles are 25x25 while your map uses 4x4 tiles! That's unusual but luckily doesn't invalidate the suggestions I made.

That's the old screens (back when I had a "resolution" for the radar-map), at the moment I have 25x25 sized tiles on the main screen and I pick a background color on the radar-map for every single pixel on the map (100x100 pixels).

@HammerBlade:

I think I got what you mean, now. Fog-of-war does show up on the radar, but the background of the radar-map is always going to be drawn, because it's non-static, without recalculation, which is very, very fast. The units are really quick to plot as well, so I think it's actually faster to just iterate through existing ones and draw that pixel than it is to check for each one, whether it's under fog-of-war or not... That last part is what you meant, right?

Thanks for the feedback, everybody!

[HammerBlade]

I think I got what you mean, now. Fog-of-war does show up on the radar, but the background of the radar-map is always going to be drawn, because it's non-static, without recalculation, which is very, very fast. The units are really quick to plot as well, so I think it's actually faster to just iterate through existing ones and draw that pixel than it is to check for each one, whether it's under fog-of-war or not... That last part is what you meant, right?

Yes, that is what I was referring to.  Well, if the units draw fast enough to justify checking each pixel for where units are on the map and drawing them, then I guess it'd be more trouble than it's worth to do an additional check for whether units are hidden by fog of war or not. 

[DoorKnobHandle]

Exactly. I'll investigate that, though. Thanks for the food-for-thought!

Little update: I'm currently working on a better shadow-system. If it fails, I still have the old one to fall back to (which was working and looking just fine already). What I'm trying to accomplish is getting rid of that shadow-overlapping-phenomenon - if two or more shadows overlapped each other with the old shadow-system, the overlapping part would be drawn even darker. That's not realistic, if shadows from one light (sun) overlap each other, they are not "added up".
      So, the new system basically consists of one empty dynamic-sprite that covers the whole screen. Every unit then draws its shadow (as long as its actually on the screen, of course) onto that sprite, which is then tinted to look like shadow and drawn. This way, if two shadows overlap, the overlapping part should be exactly as dark as the single shadows are etc. It's not there all the way, yet, but I'm pretty sure I'll manage to get it to work properly these next days.
      Also, I have changed the colors of the selection-marks, the health-bar and the selection-rectangle (which you draw to select multiple units), I wasn't satisfied with that bright-almost-white-look, they are now dark grayish, parts are almost black, plus the healthbar over selected units looks a bit "rounded" now. I don't want to post another screenshot this soon, but I'll make sure to show it off in the next image-material.
      Last but not least, I have started improving some sprites, the factory-building you can see on almost all screens looks better now.  You can see it has changed from the oldest screenshots to that newer one. Now it has changed even more, though slightly. I'll try to not only add new, but also improve existing artwork until it all looks as good as I think it should, even if it takes a lot of passes on some stuff.

[.M.M.]

And it is really from AGS??? Unbeliveable!!! :o :o

[DoorKnobHandle]

Hehe, thanks, Mirek CZ!

I thought I'd give you another update on how progress is going. With all the game-in-production-activity going on at the moment, if you don't have any news for 30 days, you're pretty much on the third or fourth page... (Not that I don't welcome all the productivity though).

Little update:

I haven't been able to do very much in the last months, but I did introduce a new unit, the marine (or trooper) so far and I can also show you the new color-scheme for the selection-marks and -rectangle:

I'm currently thinking about rewriting parts of the GUI system (mainly the part that has to do with the six buttons on the lower-right corner of the screen, the part that allows you to build new units and structures if you have a worker or a facility selected and cast "spells" - I put that in quotation-marks because there won't be magic-spells in the game, as in, real magic, that's just a technical term for special abilities/weapons, for example a unit could send an emp-shockwave every now and then etc).

I'm also thinking about a way on how to handle the creation of units. At the moment, if you queue up 3 workers to be built in a factory, it will build the first and spawn it directly in front of the building, then if the second one is ready it will try to spawn it and if that space is occupied, it won't spawn it and leave a message. I'll have to implement a simple system that tries to find a spot that is yet unoccupied and the closest to the factory. So it will create new units around the building and if it's surrounded entirely it will start spawning units a little further away, etc. It's not that hard, but a little annoying to implement if you don't fix your unit positions to tiles (like some games did) but rather have them move around freely anywhere (like for example StarCraft does, most notably in the editor, StarEdit, when you place a unit you can't really place it anywhere you want, not only on tile (5,8) and then it jumps left a tile for example to (4,8)).

[TwinMoon]

Um, totally missed this thread, but just wanted to say:

CHRIST! You're kidding right? RTS in AGS? If I could send you a beer by e-mail, I would!
From the screenshots it looks very Dune 2-like, which I think is great.

I'll have to implement a simple system that tries to find a spot that is yet unoccupied and the closest to the factory.

What about moving the first soldier after it's created so it's out of the way?

No pressure intended, but get a demo out soon!

[R4L]

Just a suggestion. I apologize if you've mentioned this somewhere.

Are you adding hotkeys as well? Or is it all point and click?

Also, the new color scheme for selecting units looks nice, and the addition of a trooper unit is nice as well.

Keep it up dkh. 

[dirk delshire]

I've played a few RTSs before Starcraft etc. and I constantly annoyed by enemy AI. I know it's very hard to program without constant feedback by real humans on how to implement battle strategy. I'm no expert but I know one thing that would make your game stand out.
The thing I'm talking about is the AI's view of the board.
If you want the game to be good you should program in a fog of war view into the AI. In most games AI looks at whatever's on the board and goes for the biggest threat to him this works basically but is unfair to the player as they cannot see the whole board at once. What I propose is hard but not impossible.
I propose that you give the AI a feature that mimics human viability and also has the AI use a random path each time to discover more of the map as he progresses making conclusions depending on what he can see. Such as  if he can see enemy units he'll either chase after them in that direction dumbly if hes set to an easy level or he'll try to plan a strategy based on how much he can see of the enemy units or bases. This will make the game far  better than some other that use the aforementioned method.