Temple of The Roguelike Forums
Development => Programming => Topic started by: Serefan on December 08, 2013, 01:31:31 PM
-
I've been working on a (turn-based) roguelike engine for a while now and yesterday I did some tests stuffing a level with a large number of enemies. Naturally, the game started hanging.
First off, how I've implemented the logic part of my game loop. It makes use of two lists: one containing the currently active physics (objects and actors being thrown around, explosions, etc.) and one containing the actors inside the level. This list of actors is sorted by their action value. The first actor in the list is always the next one to make a move, and each time an actor executes his move, his action value is increased by a certain amount, depending on the cost of the move, and he is re-entered in the list. Here's how I implemented the entire thing:
do
{
if(physics.size > 0)
// Check all active physics events, remove those that are finished
else
// Check active actor event, if finished, update actor position in list, and start next actor event
if(physics.size > 0)
// Execute all active physics events
else
// Execute active actor event
}
while((renderer is empty) AND (current actor event is not the player))
To sum it up: as long as it's not the player's turn, I keep iterating over the active events, but the loop takes a break if something changed the player's field of vision. (I realize I could optimize this a bit more, only breaking if a physics event changed player's field of vision, not actor events, but this is not the issue)
In most cases this works well. And having lots of actors in one level is not something that should happen often, if at all. The results of the tests were more or less as follows: the loop takes slightly more or slightly less than a millisecond to execute each event. With 50 actors in play, this amounts to 50 milliseconds. Not ideal, but manageable for a turn-based game. Naturally, this scales linearly. 500 actors equals half a second, which is obviously too much for the game loop.
Now I'm not saying I want levels around with hundreds of actors. But I am however planning on having scenes in my game like a bustling town, with shops, taverns, etc. where the characters inside have a somewhat realistic routine, tending to their needs, going to work, going to sleep... And I feel like my current approach will ultimately be terribly unfit for stuff like this.
So, I'm curious if there are any better practices out there for handling stuff like this. Is there a way to reduce the time my current system takes? Are there any better systems out there I'm unaware of? Should I instead look out for a system that provides a better way of handling levels as a whole (I'm thinking, for example, dividing it in chunks, but I'm not sure how to go about doing this effectively)? Would I be better off implementing a real-time system akin to that of Dwarf Fortress, so the actor's events will naturally be spread out over different frames?
-
and he is re-entered in the list.
What actually this means? And why there are two lists?
One way to speed up is simply limit the distance where action happens. And/or limit the amount of actions each actor has outside that distance which means those outside the range will perform only simple tasks, like moving etc.
-
Your update loop sounds rather slow regardless of how many actors are on the level. From your description (correct me if I'm wrong) with 50 actors your update loop is 20 times a second. This is without rendering. As a rule of thumb I think you should be able to do twice that without much trouble.
What language are you using? What platform? What functions are taking the most time according to your profiler?
-
I only know of three ways to improve performance:
- Do less work.
- Use a more appropriate algorithm.
- Use a more appropriate data structure.
You may want to try a list that automatically sorts itself or try resorting the list in place rather than removing the actor then adding it again. Collections often have built in methods that have low level optimizations - especially in higher level languages. Try to stick to using those.
The best option by far is to do less work. One thing I did for one of my games is to make creatures stay idle until the player sees them or they take damage (from traps, etc). That way most creatures aren't really involved in the update loop. Another thing is that you may be able to cut down on the amount of animations or use less granular time slices. It's hard to say without knowing how your physics events work but I'd guess that reducing the number of times you loop through before returning to the player will have the largest benefit by far.
And of course, profile everything and focus on what takes the most time.
-
Chances are it's not the loop itself that's the problem, but what's going on inside the loop. Maybe the actors or physics events are too involved, ie the AI is too complex or inefficient?
-
I'm not a fantastic coder so keep that in mind.
There are 2 questions that maybe will help:
1. Do you need to be updating guys that are off screen? How far off screen?
2. Is a bustling town going to have more than 50 moving actors on screen at once?
Others can surely help you speed this up with more efficient coding, but after that then one big work around I've used is to not compute things too far away from your character.
If you do need them to move around a bit to give the illusion of a living world then simplify their behavior off screen. Something like a drunken walk instead of a complex decision tree.
-
Your update loop sounds rather slow regardless of how many actors are on the level. From your description (correct me if I'm wrong) with 50 actors your update loop is 20 times a second. This is without rendering. As a rule of thumb I think you should be able to do twice that without much trouble.
What language are you using? What platform? What functions are taking the most time according to your profiler?
About the 50 actors -> 20 times a second, you are partially correct; it is the worst-case scenario. That is assuming every actor always takes a turn, after the player takes its turn. In practice, this varies a lot due to energy differences, since different actions consume different amounts of energy. Also, since this is a turn-based game, the game spends most of its time doing nothing, and checking the player's input. Are you saying 50 actors should be updating faster than 20 times a second?
This project is written in Java, and I'm using Eclipse. I have worked on the renderer for a long time, it pretty much works at optimal speed (this is a graphical roguelike). In those worst-case scenarios where every actor takes its turn after the player, this logic part definitely takes the most time.
Chances are it's not the loop itself that's the problem, but what's going on inside the loop. Maybe the actors or physics events are too involved, ie the AI is too complex or inefficient?
I forgot to mention, this test was made without using any actual physics events and with a stupid 'walk-to-a-random-next-square' AI, so this is definitely not the issue. Everything executed by this piece of code were empty placeholder events.
You may want to try a list that automatically sorts itself or try resorting the list in place rather than removing the actor then adding it again. Collections often have built in methods that have low level optimizations - especially in higher level languages. Try to stick to using those.
That's already in there. My actor list is a type of queue (Java's PriorityQueue), which is optimized to take only the head of the list, and is automatically sorted based on the actor's action energy.
and he is re-entered in the list.
What actually this means? And why there are two lists?
One list keeps the currently active physics events. The other (the PriorityQueue) keeps the actors that are currently in play. The idea is that there is always only one active event, since it's a turn based game; but the execution of this event can result in a few physics events, of which there can be more than one at the same time and should execute simultaneously.
Example: a wizards zaps a fireball in the direction of a group of other actors. The flying fireball is a single physics event (a projectile event). Once that event is complete (impact of the fireball), the explosion triggers knockback on the entire group of actors, thus a projectile event is thrown for every actor caught in the blast, throwing them all back at the same time.
I only know of three ways to improve performance:
- Do less work.
- Use a more appropriate algorithm.
- Use a more appropriate data structure.
The best option by far is to do less work. One thing I did for one of my games is to make creatures stay idle until the player sees them or they take damage (from traps, etc). That way most creatures aren't really involved in the update loop. Another thing is that you may be able to cut down on the amount of animations or use less granular time slices. It's hard to say without knowing how your physics events work but I'd guess that reducing the number of times you loop through before returning to the player will have the largest benefit by far.
And of course, profile everything and focus on what takes the most time.
Like I said, this was purely a test of the logic loop. Animations, physics, and AI calculations were taken out for this test. As far as I know, I have to agree with you, what I need is a better turn-based algorithm for my list, and/or a better data structure for my level. I'm just not sure what I need, that's what I'm here for.
1. Do you need to be updating guys that are off screen? How far off screen?
2. Is a bustling town going to have more than 50 moving actors on screen at once?
Others can surely help you speed this up with more efficient coding, but after that then one big work around I've used is to not compute things too far away from your character.
If you do need them to move around a bit to give the illusion of a living world then simplify their behavior off screen. Something like a drunken walk instead of a complex decision tree.
1. I'm not sure, actually. I definitely want guys that are kinda near the screen to be somewhat useful. One of my questions/ideas was using a chunk-like structure for very large levels, and like some of you said, limit the region that's being updated. I'm just not sure how this data structure is best implemented, that's what I'd like to know. One thing of note I forgot to mention is the fact that my level grid is contained in a much simplified version of a quad tree.
2. Well, if I had to take a guess, there would be very few, if no occasions where there actually are 50 actors on screen. 50 actors or more in an entire level however (which could possibly be divided into pieces given an appropriate data structure) would definitely be more frequent.
-
Are you saying 50 actors should be updating faster than 20 times a second?
A roguelike should be able to handle that without performance problems.
-
Are you saying 50 actors should be updating faster than 20 times a second?
A roguelike should be able to handle that without performance problems.
That is neither a yes nor a no; I can't really deduce anything from that statement. Let me be clear about this: Unless that number on its own is a problem, I don't really seem to have any performance problems. I simply did an (as of now) unrealistic stress test, and I was wondering if there were any commonly used data structures or algorithms out there that could help when actually trying to deal with hundreds of entities.
-
For your actor energy system, use this (http://roguebasin.roguelikedevelopment.org/index.php?title=An_elegant_time-management_system_for_roguelikes) (or reference the other Basin articles on the same topic). It's a really fast method that doesn't require repeated sorting. This may be more or less what you're already doing? In any case, if a program is slow and you want to know why, profile it. Once you fix whatever the bottleneck is it'll definitely be faster than what you've got now. Try not to optimize before profiling--you'll probably end up wasting a lot of time.
-
@Thales, right, you haven't mentioned your profiler results. You have a lot of robust profiling options with Java so that should be your first step.
Regarding 50 actors at 20 updates a second, yes, that is too slow. You should get at least 40 updates a second (with rendering, animation, etc.) with no problem, especially with Java, which is relatively fast.
-
That is neither a yes nor a no; I can't really deduce anything from that statement.
What I mean is that regardless of whether or not your 50 actors need to be updating more than 20 times per second (they may, but it depends on the game) your program should easily be capable of performing twice that. The fact that it struggles to do so suggests a problem exists somewhere. I can't offer a good suggestion because I don't know enough about your code to say where the problem lies.
-
Also, since this is a turn-based game, the game spends most of its time doing nothing, and checking the player's input.
I think you might utilize this. Most of the actors who do not actually interact with the player (for a simple example, all those outside of player's FOV) may be calculated in advance while waiting for the player's input, from closest to player to farthest. The main idea is to calculate as much as possible during the time game has nothing else to do.
This will increase game engine/logic complexity. There must be some way to check if precalculated move conflicts with actual state. Game data must support some level of parallelism. However, this approach can make an impression of all the actors being handled.
-
This list of actors is sorted by their action value. The first actor in the list is always the next one to make a move, and each time an actor executes his move, his action value is increased by a certain amount, depending on the cost of the move, and he is re-entered in the list.
Does it have to be this complex? I'm using a power value for each creature, increasing it each turn and when it's full the creature can make the move. If it's not, the creature is skipped. I don't know what is the idea in sorting the list. Why would you need to do that?
-
For your actor energy system, use this (http://roguebasin.roguelikedevelopment.org/index.php?title=An_elegant_time-management_system_for_roguelikes) (or reference the other Basin articles on the same topic). It's a really fast method that doesn't require repeated sorting. This may be more or less what you're already doing? In any case, if a program is slow and you want to know why, profile it. Once you fix whatever the bottleneck is it'll definitely be faster than what you've got now. Try not to optimize before profiling--you'll probably end up wasting a lot of time.
I just want to say I agree wholeheartedly with this. Always profile and optimize the bottlenecks. The problem could be very far from what you think.
-
@Thales, right, you haven't mentioned your profiler results. You have a lot of robust profiling options with Java so that should be your first step.
Regarding 50 actors at 20 updates a second, yes, that is too slow. You should get at least 40 updates a second (with rendering, animation, etc.) with no problem, especially with Java, which is relatively fast.
Yes well to be honest Eclipse seems to have its own profiling system. I've tried getting the profiler to work but I didn't manage to do so as of yet (I've never done this before), what little information I found on the internet didn't work for me. I must have been doing something wrong but I don't know what, the profiler kept ending up without any data.
That is neither a yes nor a no; I can't really deduce anything from that statement.
What I mean is that regardless of whether or not your 50 actors need to be updating more than 20 times per second (they may, but it depends on the game) your program should easily be capable of performing twice that. The fact that it struggles to do so suggests a problem exists somewhere. I can't offer a good suggestion because I don't know enough about your code to say where the problem lies.
This data wasn't calculated from my entire game loop. I implemented my own little debugger system, and I calculated the time taken for each piece of the game loop independently. Input checking and rendering were next to none. These numbers you're talking about were calculated from the logic update independently, so I don't understand how the problem could lie elsewhere.
Also, since this is a turn-based game, the game spends most of its time doing nothing, and checking the player's input.
I think you might utilize this. Most of the actors who do not actually interact with the player (for a simple example, all those outside of player's FOV) may be calculated in advance while waiting for the player's input, from closest to player to farthest. The main idea is to calculate as much as possible during the time game has nothing else to do.
This will increase game engine/logic complexity. There must be some way to check if precalculated move conflicts with actual state. Game data must support some level of parallelism. However, this approach can make an impression of all the actors being handled.
That's a great idea, thank you. The decision on what move to make for each character is a little object of its own making it perfectly manageable to check those conflicts even after I expand my action possibilities.
This list of actors is sorted by their action value. The first actor in the list is always the next one to make a move, and each time an actor executes his move, his action value is increased by a certain amount, depending on the cost of the move, and he is re-entered in the list.
Does it have to be this complex? I'm using a power value for each creature, increasing it each turn and when it's full the creature can make the move. If it's not, the creature is skipped. I don't know what is the idea in sorting the list. Why would you need to do that?
No I don't have to do it this way at all. It's simply the first thing I thought of. I don't see why you would consider it complex though, it kinda reminds me of the FFX battle system: next guy to make a move does his thing, then he moves up the list, repeat.
The priority queue, according to oracle, should be optimized to poll for the next element in the list, as well as sorting an already nearly sorted list, so I took that and went with it. Correct me if I'm wrong, but what you're suggesting here is that the sorting procedure specifically is taking the most time? I was planning to check up on that, so I'll get back to you on that.
I suppose I could use that power value idea, or more specifically, I'd do the opposite, decrease it each turn and make a move when zero, that way I can easily account for actions taking in different amounts of time. I'd have to change the way the game waits for the player to make a move though. As it is now, since there's only one actor event active at any given time, the player's event is simply an extension of the normal actor event that suspends its execution until the player has decided on his move.
-
Huh, creepy. I decided to keep it as it is until I worked out a good idea from what I've gathered here, and moreover until I actually came around to implementing the big city level. The only thing I did yesterday was install a new version of Eclipse. I decided to run another test with 500 little minions running around... And execution time is around one third of what it was yesterday. Someone either explain this to me or send me a bible and a crucifix to protect me against this witchcraft. :P
Also, I tested the speed of re-inserting the actor in the list while I was at it, and that actually happened extremely fast. The list re-ordering is definitely not an issue.
...I did also have my laptop tumble to the floor though. Maybe it learned it's lesson and decided to be good.
-
Find a profiler that works. It doesn't have to be perfect and it doesn't have to be integrated in your IDE. It just has to tell you which function is so inefficient that processing a single actor takes a whole millisecond on a modern CPU.
-
Worst case scenario you could compare the CPU time before and after running certain sections of code.
-
Worst case scenario you could compare the CPU time before and after running certain sections of code.
Like I said, that is exactly what I did.
-
Honestly I feel most responses here are really besides the point of what I actually asked. Everyone's focusing on this profiling and optimizing this tiny piece of code which is really not my priority. All I wanted to know was if there are any established structures that can be used when playing around with levels that are too large to update using simple strategies like this one, for example some kind of level partitioning system.
-
Some rough calculations:
Inserting an event to a priority queue takes roughly log(N) operations, where N is the size of the queue. (Assuming the priority queue in Java is implemented with a heap, or another data structure suited for this purpose.)
Moving a creature in a random direction takes roughly 100 operations. Probably less. Depends on how exactly it is done.
A computer performs roughly 100 000 operations per millisecond (actually more).
With 500 actors, we get 500*(100+9) = 50000 = 0.5 ms. You would need to have 100000 actors (120 ms) to have problems with this.
Even if the list of actors was dumb (N operations to insert), with 500 actors you would still get 500*(100+500) = 300000 = 3 ms.
If you have problems with 50 actors, then the problem must be elsewhere. That's why people are suggesting you to use a profiler.
-
Honestly I feel most responses here are really besides the point of what I actually asked. Everyone's focusing on this profiling and optimizing this tiny piece of code which is really not my priority. All I wanted to know was if there are any established structures that can be used when playing around with levels that are too large to update using simple strategies like this one, for example some kind of level partitioning system.
The reason nobody has been able to give you what you want so far is that you haven't provided anything like enough information to let us figure out what the problem is. The optimum way to arrange your game-loop will depend entirely on which operations are taking the longest time to run, which we don't know and you probably won't know either until you get a profiler working. There is no one-size-fits-all answer here besides 'find out what is taking all the time and try to do it less'.
-
The reason nobody has been able to give you what you want so far is that you haven't provided anything like enough information to let us figure out what the problem is.
That's the whole thing - I don't have a problem that needs to be fixed. I was asking a hypothetical question. The question being whether there are any established methods out there for handling environments that are simply too large to simply handle in their entirety. From what I'm gathering here the answer would be no - which would be a perfectly fine answer by the way; I just wanted to make sure I didn't miss anything while looking for one.
-
For your actor energy system, use this (http://roguebasin.roguelikedevelopment.org/index.php?title=An_elegant_time-management_system_for_roguelikes) (or reference the other Basin articles on the same topic). It's a really fast method that doesn't require repeated sorting. This may be more or less what you're already doing? In any case, if a program is slow and you want to know why, profile it. Once you fix whatever the bottleneck is it'll definitely be faster than what you've got now. Try not to optimize before profiling--you'll probably end up wasting a lot of time.
Actually the scheduling method used by the OP is much better IMO. I think the article you linked contains an error (AFAIK Crawl has no monsters of speed 100 and 101, it made a decision to have no monsters with such small differences in speed, and I believe it is a conscious and sensible decision). Also it likes ADOM's time management system, which has its weird effects: when running from an enemy of the same speed, I sometimes get two moves while the enemy does not move, then the enemy has two moves while I am skipping. This seems to be an artifact of the speed system used (if I move in segment X, then my next move is sometimes in segment X+9, sometimes in segment X+10, this is not synchronized with the enemy, and that's why we get the weird effect). I suppose the same would happen with the system described in the article.
Also checking energy > 0 on each tick is not that efficient, especially if you want to be accurate and have many ticks per move. A good priority queue does not do repeated sorting on each insertion, it is much more efficient (if you are checking an actor 10 times per move like ADOM does, the efficiency is comparable, but accuracy is very low).
-
I wasn't too focused on what the OP was actually using, or if that was even the problem (because it's most likely not), just thought I'd throw those articles out there for him to look at since he was talking about sorting and action systems. I should've left that off because the real problem was lack of profiling.
Not to derail the discussion, but highly granular action point systems that can result in extra moves here and there are not necessarily a bad thing for non-puzzle oriented games. It can depend on the style of the game, enabling very complex movement systems in games where speeds are highly dynamic, anyway. Even if not dynamic, how many players actually notice the difference between X+9 and X+10? (I would still agree that static relative movement speed is the way to go in most games, though. And as a side note, it seems the problem with DCSS movement is it does away with variable relative speeds by making certain values meaningless.)
-
I think that a monster with speed equal to PC's should move each turn (where "turn" is defined as the interval between two player moves), slower monsters should sometimes skip turns, and faster monsters should sometimes get an extra turn. In ADOM, sometimes a monster alternately skips a turn and makes two moves. This is bad in more tactical games (harder to plan), and even in less tactical ones it makes no sense IMO and is annoying. (I do not see X+9 vs X+10 either, but I infer this as a reason for this behaviour.)
In my smaller games (Hydra Slayer and HyperRogue) speeds are always powers of two (normal, 2x slower or 2x faster), this approach allows the player to plan their movements easily, which is good for tactics.
Could you elaborate on the problems with DCSS movement?
-
Ah, wasn't thinking about actors actually skipping a turn only to later make two consecutive moves. That does seem somewhat odd. I was only thinking about getting (or losing) the occasional odd move, which seems reasonable. (I never played ADOM for very long since the early game repetition started grating on me, so I didn't have a chance to notice that.) Strange that occurs in ADOM though, since an simple energy based system doesn't seem to result in that effect. Maybe I'm thinking about it wrong.
Imagine an energy system whereby all actors get 100 points per turn. Assume the player requires 100 energy to move, and therefore moves every turn. A monster that requires 110 energy to move will skip its first turn (not enough energy to move yet), then move every turn after that for 10 turns before skipping one turn, then the cycle repeats. I think the true cause is that it gets a lot more complicated once there are actions other than movement thrown in.
I'm not too familiar with the intricacies of DCSS movement mechanics, but know it uses different time systems for the player and monsters, which isn't practical for other games where the player has access to specific movement values, which ideally should be consistent and comparable. About certain values, see this (https://crawl.develz.org/mantis/view.php?id=7396).
-
That's the whole thing - I don't have a problem that needs to be fixed. I was asking a hypothetical question. The question being whether there are any established methods out there for handling environments that are simply too large to simply handle in their entirety. From what I'm gathering here the answer would be no - which would be a perfectly fine answer by the way; I just wanted to make sure I didn't miss anything while looking for one.
Fair enough - I apologise for misreading your intent. One thing you could do if you want to have large environments and don't want to simply freeze parts of it is to have a separate, simpler, system for actors which are beyond a certain range from the player. If they are out of sight range exact movement speed is unlikely to be all that important - you could simply assume that far-away actors all move at the same speed and move them into a separate queue that processes each actor in turn and so doesn't need sorting or energy counting (until they move closer to the player again).
In my smaller games (Hydra Slayer and HyperRogue) speeds are always powers of two (normal, 2x slower or 2x faster), this approach allows the player to plan their movements easily, which is good for tactics.
Generally speaking, I greatly prefer this kind of approach over more free-form timing systems, which make it hard to keep track of creature movements and feel slightly fiddly. It also seems a bit silly to me to rigidly partition space into a grid but then not be prepared to do the same thing to time.
That said, I am thinking of having a variable-movement-speed mechanic in my next game, but it will be one where movement between tiles is animated and actors can freeze 'in between' tiles during the player's turn, so that the turn order should still be fairly obvious.
-
In an efficient language like Java it's quite easy to have thousands of actors each moving several times per second (by the wall clock), on a map with hundreds of thousands of tiles. I didn't find the OP very clear, but it didn't sound like there was anything in the system described which would prevent simulation of that scale being carried out efficiently. The alternative time systems are well-used and reliable, but shouldn't have Certainly a desktop or laptop made in the last 10 years shouldn't have any performance-related reason to use any kind of special treatment for "out-of-range" monsters on a scale smaller than that, though there may be good gameplay reasons to do so.
The reason nobody has been able to give you what you want so far is that you haven't provided anything like enough information to let us figure out what the problem is.
That's the whole thing - I don't have a problem that needs to be fixed. I was asking a hypothetical question. The question being whether there are any established methods out there for handling environments that are simply too large to simply handle in their entirety. From what I'm gathering here the answer would be no - which would be a perfectly fine answer by the way; I just wanted to make sure I didn't miss anything while looking for one.
I'm not sure you meant by "an environment too large to handle in its entirety" - if you mean the number of tiles on the map exceeds the memory of the JVM, that can be compensated for by saving out-of-range areas to disk. Except for AI pathfinding (which should be used sparingly on large maps), map size shouldn't have any effect on the time it takes to process a turn. I assume that the actors and map tiles are double-referenced, so that the occupant of a tile and the position of an actor can both be found in constant time.
Either way, the answer to your hypothetical question is there are, but theoretically they shouldn't be much better than the method you described. However, all of those systems should be able to give better performance than what you described.
What time periods were you measuring in your timing system? Did you actually create a scene with hundreds of actors and measure the time it took to process a turn, or did you measure the time it took to process a single event? What was the precision of the clock system you used? If the smallest unit of time it can measure is a millisecond, then you may have a very fast system that's being diagnosed with a nonexistent problem.
-
I think the OP does have a problem that needs to be fixed, if they're reaching for a new, probably more complicated solution to a performance issue that shouldn't exist in this case (as far as I know).
@Thales, can you post a working example of your code so people here can run it?
-
I'm not sure you meant by "an environment too large to handle in its entirety" - if you mean the number of tiles on the map exceeds the memory of the JVM, that can be compensated for by saving out-of-range areas to disk. Except for AI pathfinding (which should be used sparingly on large maps), map size shouldn't have any effect on the time it takes to process a turn. I assume that the actors and map tiles are double-referenced, so that the occupant of a tile and the position of an actor can both be found in constant time.
Either way, the answer to your hypothetical question is there are, but theoretically they shouldn't be much better than the method you described. However, all of those systems should be able to give better performance than what you described.
What time periods were you measuring in your timing system? Did you actually create a scene with hundreds of actors and measure the time it took to process a turn, or did you measure the time it took to process a single event? What was the precision of the clock system you used? If the smallest unit of time it can measure is a millisecond, then you may have a very fast system that's being diagnosed with a nonexistent problem.
- Yes, actors and map tiles are double referenced.
- Like I said in a previous comment, I had quite an increase in performance since yesterday.
- I measured both the entire turn and the single events, both in milliseconds and nanoseconds. What I posted here wasn't really all that accurate because I wasn't expecting you guys to actually focus on that, it was more of an fyi.
Lastly, I have to mention this game won't really be following standard roguelike format. I suppose you could consider it more of a blend using roguelike and RPG elements. The major focus of the game's programming will be on rather complex AI routines. Basically, instead of having a great deal of randomly generated monsters, the overworld will be more static in its layout, populated with NPCs that each can have a small to large impact on the story; the player will actually be spending a lot of his time exploring the narrative of the game instead of trying to improve his character.
I suppose I can sum it up nicely comparing it to 'Dwarf Fortress in a predefined world'. In any case, yes, there will be quite a bit of pathfinding in play. Not necessarily over huge distances, but quite a few of them at the same time.
I think the OP does have a problem that needs to be fixed, if they're reaching for a new, probably more complicated solution to a performance issue that shouldn't exist in this case (as far as I know).
@Thales, can you post a working example of your code so people here can run it?
No, buddy, I can't. I'm planning on posting an example once I finished the demo chapter but not sooner. Please, I appreciate you all telling me what I had was inherently too slow, but don't worry about that. I can manage that part.
Here's another, maybe better way of putting this whole thing: Don't worry about the amount of time it takes for a single actor event to execute. Let me worry about that. What I'm interested in is ways of optimizing the total amount of time it takes per actor in the level. As it is now, the total amount of time increases linearly with the amount of actors; since I check up on all of them in the same way. A good example was the person telling me to predict the actor's movements ahead of time while the loop's idle, waiting for player input.