Temple of The Roguelike Forums
Development => Programming => Topic started by: Destroid on June 26, 2012, 01:17:10 PM
-
Hi, I'm very new to designing roguelikes (and pretty new to gamedev in general) and was hashing out a few ideas, and one of them was the timing system. In the end I thought a good system to do RL timing would be to have an array store all of your actors, and each engine tick step through the array to see if any actor is ready to act. Readyness will be measured by a cooldown timer (or timers) that when they reach 0, the actor may take an action, filling it's cooldown back up again to an appropriate amount.
Then at one stage I looked over the time system section at roguebasin (http://roguebasin.roguelikedevelopment.org/index.php?title=Time_Systems), and reading the systems there left me more confused than enlightened. They talk about ordered queues and the like, but I really don't understand the benefits of having such a thing, versus (what I perceive to be) the simpler system outlined above. Is there something I'm missing? Is my system a variant on a standard but I'm just not getting it? Or is there a good reason to re-order actors, or use a queue?
-
Either method is fine. The queue thing can be faster on the CPU (not a worry) and maybe has design advantages, but it's probably better to stick to something that you understand.
-
The benefit of a queue is you can jump efficiently to the actor whose turn is next, you don't have to scan through all the actors and find the one with the lowest cooldown. But I suspect the performance difference is irrelevant on modern computers unless you plan on having thousands of actors.
I went with a queue and I regret it now because it took so long to implement and it just makes things more complicated. If I was starting again I would go with the array approach and only switch to a queue IF the array approach wasn't performing. I am betting the array approach will be fast enough. I suspect the processing of the actors actions takes a lot more processing time than working out who acts next anyway.
-
Great to know, thanks!
-
Suppose you have 1000 monsters (like in ADOM's animated forest), each of them roughly as fast as you (one move per game second), but with a different time offset (the first move of monster number i is at i game milliseconds). If on each game millisecond you are looking for the monster which moves next, you will compare 1000 monsters per game millisecond, which is 1000000 compare operations per each game second. If you are, say, resting for 500 turns, then it will take 500 million operations, which will take roughly a second of real time (depending on the computer and programming language).
Now, the RogueBasin article is misleading. It suggests that you keep the list of actors ordered by time, instead of an unordered one. As you have noticed, there is no obvious benefit in this approach (although it takes 1 operation to find the next actor, it may take 1000 operations to move the actor to its correct position after updating their time, and the two balance each other).
On the other hand, there are effective implementations of priority queue (http://en.wikipedia.org/wiki/Binary_heap), where the actors form a tree-like structure (instead of an ordered list), and it takes 1 operation to find the next actor, and only ~20 operations to move the moved actor to the right position. Thus, you perform roughly 20 operations on average, instead of 1000. Thus, the number of operations for 500 turns will drop down to (roughly) 10 millions, which will be executed instantly.
As you can probably see, in most cases the simplest approach is sufficient. It is not a problem to have resting take 1 second of real time in extreme circumstances.
-
Could this become an issue if you are working in a slower language like python?
-
I expect it to be fast enough in Python... I am not sure.
Which means that you should do as Omnomnom says. Try the simplest possible way. Only when the game starts running too slowly, you should use some kind of profiiling (or intuition) to determine the part which causes problems, and optimize it.
-
A binary heap is really simple to implement. I think I have it as about 50 lines of code. You just need to know how to insert and how to remove. It's probably not as hard as you think and since it is a standard you can look at probably tons of examples. The thing is that a binary heap is the fast option in other parts of your code. Another place I use it is in the a* pathinding, because a bin heap is faster than other options, such as a list and whatnot. As Z said, it probably won't make a significant difference in most cases, but if you come from a programming background or are confidant in your ability to learn I would suggest you implement it because why not?
-
It's hard to imagine actually needing to implement a heap. Standard libraries for pretty much any language will provide one, almost certainly superior in quality to any handroll. And yes, I agree it's best to go this route and not shy away from concepts just because they may be new to you. A heap is a useful abstraction; embracing it will simplify your program (and your reasoning about it) in the long run.
-
When I did Sun Crusher I made all objects 'pause' until after the player had taken their turn, then they all were allowed to move. They would then 'pause' again once they'd moved (terrain moved, space stations just fired shots).
I couldn't figure out how to check that everything had moved, so I just let the player move again after like 1.5 seconds of real time...surely all the objects on the screen had finished by then, right? Wrong. Sometimes enemy shots fired would still be flying, so if the player were quick enough he could dodge them.
The work around for this was really embarrassing. Every time a bullet object was created it reset a global timer. I figured out the max flight time from one end of the screen to the other, and set the timer to that. The player was paused until that timer went off....So several dozen bullets are firing, resetting a timer over and over...grah!
There were more completely stupid and noobish work arounds, but I learned a lot, and the game was sort of unique. So it was a success. Just please never ask for the source. Ever.
I'll never do it like that again. :-)
-
It's hard to imagine actually needing to implement a heap. Standard libraries for pretty much any language will provide one, almost certainly superior in quality to any handroll. And yes, I agree it's best to go this route and not shy away from concepts just because they may be new to you. A heap is a useful abstraction; embracing it will simplify your program (and your reasoning about it) in the long run.
+1.
The actual usage of advanced data structures, particularly in java, are abstracted among a set of collection classes. They're all convertible between one another and use almost the exact same syntax. I think python does something similar. When at all possible, use standard libraries!
As for the timing- From a conceptual point of view, it might be better to implement equitable discrete timing. That is, all actions take 1 turn and every monster (and player) takes 1 turn.
Then you just take 1 turn for the player, iterate through your monsters and give them each a turn to do something, then poll the player for an action. If you REALLY want 'haste' or 'slow' or timing effects, you can apply that in the update function of a given entity-- add an extra update call or skip every other update call respectively. Missiles can similarly be simplified by describing how many tiles they cover per turn.
Additionally... you can just run updates for each monster and log each tile that is interacted with- you can easily track collisions (esp if you store positions prior to update) in a computationally minimal way.
Some people like to get into physical simulations and initiative timings and what not, but you really don't need to mess with that. The player will rarely experience the work you put into that. A turn-based game, strictly speaking, doesn't ever need to use the timer in the logic component of a game-loop.
Bind your game logic to the User-Interface. What information is relevant in the UI is all the player should care about. Similarly, it's all the coder should bother implementing. If your work doesn't reflect onto the UI in a way that informs the player to make decisions, then whatever you're doing is irrelevant.
-
In my case, the design calls for more sophisticated timing rules than you usually see in a roguelike, with highly variable amounts of time passing per action (dependant on conditions) and multiple independent cooloffs per actor, to separate out the attack and movement steps (and possibly others, but starting small here!). At the moment I am working on other projects in Actionscript 3, but I wouldn't be shy about learning a different language, although I am by now means an advanced programmer.
-
In my case, the design calls for more sophisticated timing rules than you usually see in a roguelike, with highly variable amounts of time passing per action (dependant on conditions) and multiple independent cooloffs per actor, to separate out the attack and movement steps (and possibly others, but starting small here!). At the moment I am working on other projects in Actionscript 3, but I wouldn't be shy about learning a different language, although I am by now means an advanced programmer.
AS is awesome- does a lot of work for you, but I'd recommend learning HaXe NME. It's the same syntax as AS only better in every way. They've wrapped the Flash API such that it can target multiple platforms. It's easy and accessible and more powerful- do it. www.haxenme.org.
Why the need for complex timing? How much of a role does it actually play relative to the end user as per your design?
-
What? No lols for my complete mess of a timing system? :'(
-
AS is awesome- does a lot of work for you, but I'd recommend learning HaXe NME. It's the same syntax as AS only better in every way. They've wrapped the Flash API such that it can target multiple platforms. It's easy and accessible and more powerful- do it. www.haxenme.org.
Why the need for complex timing? How much of a role does it actually play relative to the end user as per your design?
Pretty central, I'm modelling momentum, while retaining single square movement. This requires variable time. The player will be interacting directly with this system.
And Jo, that really does sound like a mess :D
-
Oh it is. And it shows. :-[ ;)
-
AS is awesome- does a lot of work for you, but I'd recommend learning HaXe NME. It's the same syntax as AS only better in every way. They've wrapped the Flash API such that it can target multiple platforms. It's easy and accessible and more powerful- do it. www.haxenme.org.
Why the need for complex timing? How much of a role does it actually play relative to the end user as per your design?
Pretty central, I'm modelling momentum, while retaining single square movement. This requires variable time. The player will be interacting directly with this system.
Couple of thoughts-
Modelling momentum with fixed spaces is going to get pretty wonky-- the player will have difficulty understanding whether a high-speed object is moving 3 or 4 tiles on the next turn, when it may make a significant difference. Perhaps even more importantly is where the high-speed object is going to be 3 turns from now. A game that is very sensitive to physics can work perfectly fine in a turn-based environment, but in a rigid playing field (tiled) it may not be a great idea.
In Dwarf Fortress, when multiple objects are standing on top of each other the UI spins a line {"|","/","-","\","|","/","-","\"} on that tile to toggle between the two symbols. You might draw from that and cycle through how many tiles an object is going to move for the next three turns. This way you can fairly represent acceleration and velocity. IE- an object is moving 9 tiles over 2 turns- the player needs to know that it is moving 5 tiles on the next turn, 4 on the turn after, and 5 on the turn after that. If the object is accelerating, it may move 5 tiles on the next turn, 5 tiles on the turn after, and 6 tiles on the turn after that. If you associate colors- like red is next turn, yellow is the turn after, and green is a turn after that-- you might have a clear way of giving information to the player.
At this point, however, you save computations by making your physical calculations work relative to tiles. You could use a 6ftx6ft space to define a tiled space and do real calculations, but the player, even if he's a physicist, isn't going to know whether you're calculating movement over real-time or over tiles.
-
I implemented variable length actions and tried it out but I am disappointed about the results and am thinking of implementing a much simpler system. It's good simulation wise but it gets unintuitive and very complicated from a gameplay perspective. Take this example:
player time to move one tile = 1
player time to melee attack neighbouring tile = 0.5
bird time to move one tile = 0.4
What the player sees if they move about is that the bird alternates between moving 2 and 3 tiles at a time: 2,3,2,3,2,3
Now if the player switches to melee attacking something (not the bird) the bird will appear to slow down: 1,1,1,2,1,1,1,2
This highlights two problems (in my opinion). First the bird slowing down is unintuitive. Why would a bird appear to slow when the player attacks and speed up when they move? This expects the player to understand the whole relative time thingy.
Second that 1,1,1,2 staggering...the player can't predict movement in this system because look there are three 1s in a row and you might think the next movement of the bird will be one tile...but no it suddenly seems to jump 2. Okay that's a common problem and a minor one, but it does limit predictability.
The biggest problem I see is that the player is expected to make critical survival decisions based on time, yet variable length actions obfuscates how time works in the game and forces them to run complicated calculations upon detailed statistics. For example imagine the player is being chased by a tiger and needs to work out if they have time to throw a javelin at the tiger and still be able to flee to a door 10 tiles away in time how do they do that? The tiger moves 121% as fast as the player. Throwing a javelin takes 78% as long as moving a tile. They are going to need a calculator. They could just guess, and that's how I would play, but I would do so knowing that my method of play was "lazy" and I was playing with a sub-optimal strategy. After losing a few times I might just decide I will never win unless I bother running all the calculations...
Another problem I found was kiting:
player time to move one tile = 1
player time to melee attack neighbouring tile = 0.8
orc time to move one tile = 1
orc time to melee attack neighbouring tile = 1
So now if the player times this right they can can wait for the orc to walk up to them, melee attack and the orc doesn't get a chance to react before the player gets to move again. The player then steps backwards and avoids the orcs attack. But this kiting only works if you time it right, which means the player has to calculate it. But this is fine because it's a simulation - except if it's a proper simulation the player should be able to choose how long they wait. Ie a variable "wait" action. Press that '.' key and get a little input field asking how many "turn units" you want to wait. 0.2 please. And now this game is just getting too complicated.
All these things can be worked around somewhat. But I am beginning to lean towards uber simplicity of just having all actions of all creatures take the same amount of time, or multiples of 2. At least that is predictable and perhaps that's what matters most of all? It's not like variable action lengths are easy to implement either. Knowing what I do now I wouldn't have bothered.
Same story with field of vision...I spent too long reading about permissive field of view and that digital one, and turns out the far more basic method is "better".
-
player time to move one tile = 1
player time to melee attack neighbouring tile = 0.8
orc time to move one tile = 1
orc time to melee attack neighbouring tile = 1
0.0 : player attack : PO
0.8 : player move : P_O
1.0 : orc move : PO
1.8 : player attack : PO
2.0 : orc attack : PO
I don't see a problem here, since they move at the same speed. The player will get extra attacks as time goes on, but it's not like the orc won't get to attack, unless I am just misreading your system. The player attacks faster so the advantage is and should be there.
I also don't have a problem with things "slowing down" when attacking versus moving. As long as the player knows attacking is faster than moving that should be fine.
The 1,1,1,2 thing I agree is a problem, although I think that strongly depends on your game as a whole in terms of whether or not it will be a serious problem. Here's a solution from the world of trpgs:
Turn List:
You
Orc
Orc
You
Orc
Orc
You
Orc
Orc
Orc
A simple list of turns can make it easier to plan ahead. This is perfect and works wonderfully if every action creature x makes takes y amount of time. If attacking and moving can vary in time then it's a little harder to make a deterministic turn loop, but it's probably doable in some fashion.
-
I did a little survey of RL time implementations some time ago,
http://kooneiform.wordpress.com/2009/04/14/roguelike-turn-based-time/
I think it'd be wise to heed the advice to reflect the mechanics in the UI.
-
I understand the interface I'm planning is quite counter intuitive and will need quite a lot of UI aids for the player. I'll post up my prototype when I've implemented a timing system in it. I don't mind if the game will be a bit more ponderous than the usual RL because I'm aiming for a more tactical experience, under the roguelike control scheme.
Not all of the problems pointed out will apply though, as I am planning to have a 0s (or perhaps very small) attack time cost, and run attacks on a separate cooldown to movement. This is to allow you to fight and move at the same time, creating a positioning game. With regard to movement - it won't have an actual move cost, the time that passes each movement turn will be the amount of time it takes for you to traverse a single square. Your movement input adds velocity to your current velocity, and then your avatar is moved one square according to that velocity.
-
http://www.mediafire.com/?h6nm8m88bafha6c
You'll need flash player to run it. The rounding is dodgy at the moment, but don't mind that.
-
It works.
I can't reasonably determine how fast I'm going.
Max velocities would be nice.
-
It works.
I can't reasonably determine how fast I'm going.
Max velocities would be nice.
Yep, it doesn't have very useful UI aids yet. But it's running on the time system I proposed, even if it's only keeping track of the player at the moment. I'll implement a monster, attack and something to make it easier to see where you are going next.
-
Stop using grid based movement
-
If I did that I would need a more sophisticated control scheme, or it would just be odd.
-
If I did that I would need a more sophisticated control scheme, or it would just be odd.
It's more odd on a grid.
Not much more sophisticated, you just need angular momentum.
-
I'm not worried about the computational side of it, the thing that I like about the RL interface is that it's very quick and simple to use. If I move away from a grid to a continuous 2d plane I need to allow for a lot more variety of inputs, and without discrete locations player mental gymnastics are more complex.
Of course, the current in my prototype is by no means easy to use, but at least it's different. If I switched to continuous position variable time doesn't really make any sense, and that's the interesting part about this idea to me.