I've watched a couple of videos where the developer demonstrates an algorithm using some visualisation and an ability to 'step' manually or set the processing speed of such an algorithm. See Casey's Killing The Walk Monster or Oskar Stålbergs's Townscaper video.
I was just wondering, syntactically, how that works. I'm used to the idea of an algorithm executing as fast as the main update loop executes, so is it as simple as setting this up to only execute on a step value and then increment that externally. It would be great if someone could break it down for me how to setup code like this in general.
I was just wondering, syntactically, how that works. I'm used to the idea of an algorithm executing as fast as the main update loop executes, so is it as simple as setting this up to only execute on a step value and then increment that externally. It would be great if someone could break it down for me how to setup code like this in general.
Edited by James Deeman
on
Reason: Initial post
the main trick is to split the algorithm with a suspend point where you save all the information you need for the rest of the algorithm into a struct and then have the function called again next frame with that struct as parameter and then just return back to the caller.
Then at the start of the function you have a switch that jumps back to the correct point in the algorithm where it can do some more steps until the budget runs out and it's time to suspend again.
Good points to put such suspend points is loops, you can put a hard limit how many iteration per frame will be executed before it suspends. (This hard limit is then the speed of the algorithm)
If your language has coroutines the compiler can do this transformation for you, but I'm not a fan of how opaque the state of those tend to be. I like knowing where a coroutine object will resume from.
This will affect how that algorithm is used in your engine though, because you cannot call it and expect to get the result back in the calling code, instead the result will be available several frames later.
Then at the start of the function you have a switch that jumps back to the correct point in the algorithm where it can do some more steps until the budget runs out and it's time to suspend again.
Good points to put such suspend points is loops, you can put a hard limit how many iteration per frame will be executed before it suspends. (This hard limit is then the speed of the algorithm)
If your language has coroutines the compiler can do this transformation for you, but I'm not a fan of how opaque the state of those tend to be. I like knowing where a coroutine object will resume from.
This will affect how that algorithm is used in your engine though, because you cannot call it and expect to get the result back in the calling code, instead the result will be available several frames later.
Another way to look at it is similarity with any physics simulation, if you have written any.
Even basic "new_pos = old_pos + delta * velocity" calculation.
When your game loop runs as fast as it can, you don't simulate million physics steps - your objects to do not suddenly arrive at their final position. They just step a bit forward. So you keep your state (position) in some external data - outside game loop. And update only it "a bit" in each iteration.
Same thing with any other algorithm you want to write. You can update only part of it in each iteration, or on user interaction (button press).
Alternative approach is to leave calculation as is - in one function everything all at once. But during calculation store intermediate results in some data structure. Whatever algorithm is calculating - put in array, based on each iteration, each step, each timestep - whatever makes more sense for this particular algorithm. Then in your main loop/rendering you can always extract any intermediate step to use for whatever you need - be it visualization, or affecting other calculations.
Even basic "new_pos = old_pos + delta * velocity" calculation.
When your game loop runs as fast as it can, you don't simulate million physics steps - your objects to do not suddenly arrive at their final position. They just step a bit forward. So you keep your state (position) in some external data - outside game loop. And update only it "a bit" in each iteration.
Same thing with any other algorithm you want to write. You can update only part of it in each iteration, or on user interaction (button press).
Alternative approach is to leave calculation as is - in one function everything all at once. But during calculation store intermediate results in some data structure. Whatever algorithm is calculating - put in array, based on each iteration, each step, each timestep - whatever makes more sense for this particular algorithm. Then in your main loop/rendering you can always extract any intermediate step to use for whatever you need - be it visualization, or affecting other calculations.
Edited by Mārtiņš Možeiko
on
Thank you very much for your answers. Sounds like it's a case of decoupling the algorithm from the main process and writing that into the code in separate 'sections' in order to present them/step them however I want. I guess it's about thinking about this from the start. I'll probably look to implement some sorting algorithms in this way to help cement the idea. Any further reading suggestions would be appreciated. 👍
If you simply print changes of unique variables with printf or a log file, you can probably create a simple program for stepping back and forward with custom visualization just like one would implement undo history as a current state and a list of reversible modifications holding new and old values. I've been thinking about making this for embedded debugging via SSH.
One of the things is looking at the state fresh every time and then deciding what to do.
For example for bubble sort the nested loop algorithm is something like:
the broken up algorithm would be something like;
with arr, i and j as the persisted state.
As you can see the most central bit (the test and swap) is preserved unchanged. Then the array bounds logic is reshuffled so that the algorithm can start with that central bit and then decide what the next step will be and return/reschedule as needed.
recursive algorithms are a more difficult but you can solve that by adding an explicit stack that you push to on the recursive call and pop at return from that call
For example for bubble sort the nested loop algorithm is something like:
1 2 3 4 5 | for(int i = 0; i<len; i++){
for(int j = i; j+1<len;j++){
if(arr[j] > arr[j+1])swap(&arr[j], &arr[j+1]);
}
}
|
the broken up algorithm would be something like;
1 2 3 4 5 6 7 8 | if(arr[j] > arr[j+1])swap(&arr[j], &arr[j+1]);
j++;
if(j==len){
i++;
j = i;
}
if(i==len) return FINISHED;
else return WORKING
|
with arr, i and j as the persisted state.
As you can see the most central bit (the test and swap) is preserved unchanged. Then the array bounds logic is reshuffled so that the algorithm can start with that central bit and then decide what the next step will be and return/reschedule as needed.
recursive algorithms are a more difficult but you can solve that by adding an explicit stack that you push to on the recursive call and pop at return from that call