COPYRIGHT AND LICENSE
The Sureal Time algorithm is a part of Interhack. Interhack is copyright (c) 1996-
1999 by Damian Bentley. Please contact bendchon@mehta.anu.edu.au for a copy
of the license. Basically feel free to copy and pass this document on - Sureal Time is
something that anyone making a roguelike game can use.
INTRODUCTION
This document describes the Sureal Time algorithm. What is it, and why was it
developed? There is a group of games available today referred to as roguelike games. They
consist of a set of levels (in most cases, dungeons), with a player running around killing
monsters, performing tasks, and in general having a good time. In many cases they are text
based, and almost all are single player.
With single player roguelike games, movement is usually turn based. In other
words, the player makes a move, and then all the monsters make their moves. In the
development of a multi player version of a roguelike game this becomes a problem as will
be discussed later.
One solution to this problem is described here. Sureal Time is the combination of
real time movement and turn based movement. It was developed by many people who have
worked on Interhack, with each change or idea adding to the advantages of the algorithm.
Feedback on Sureal Time is appreciated, including ways in which to improve this
document, or questions that have not been answered by this document.
THE PROBLEM
As it turns out, the problem is quite simple. But first we shall start with current
methods in single player roguelike games.
With a single player making moves, it is quite easy to create a simple loop where
the player makes a move until the die, quit or save. Then everything else that happens in the
game happens. That is: monsters move, checks will be made to make sure the player is
alive, and so on. Given that some roguelike games require some thought at some stages (oh
heck I am almost dead, what can I do), this is good because a player can stop and think for
as long as they want before making a move.
However when there are several players, problems crop up. If two players are in
the same room, what happens to movement? Does one player make a move, then the other
player? Can both players move at any time they want? If a player has a fast connection, do
they move faster? What happens to players that have intrinsic speed? All these problems
need to be solved in a way that is fair to players.
In addition to the problem described above, there are other aspects to be looked at.
For instance, what happens when a player looses a connection, and how do monsters now
attack players? One of the most important parts of the Sureal Time algorithm is in handling
events when a players keyboard action lags behind. What does a player do if a move is
forced in Sureal Time?
So the problem is this: When there are two or more players in close proximity to
each other, how should movement occur?
POSSIBLE SOLUTIONS
The first and most obvious solution to the problem is to use real time. Each player
has a certain amount of time to make a move before all the monsters and other events
occur. It does not matter if the player has a fast or slow connection. It does not matter home
many players are in the game. All players are placed on the same level of game play.
Real time has one major drawback: A player can not stop and think about what
move to make next. If a player wishes to spend a minute looking through their inventory to
see what they can drop, they are still under the influence of the real time - they could be
attacked at any point in time.
Another alternative is fully turn-based movement. If there are three players A, B
and C, player A makes a move, then player B, and finally player C. This repeats over and
over again. This allows players to stop and think about their next move. There is one very
obvious problem with this solution. If player B stops and looks through their inventory,
player C and player A, are kept waiting for possibly long periods of time.
Both real time and turn-based movement have their advantages. Real time allows
the game to flow on no matter what is happening. Turn based allows players to stop and
think about how the next move should be made. So why not combine both of these
solutions to form what shall be called Sureal Time. Essentially Sureal Time is like adding a
real-time time limit onto turn based movement.
SUREAL TIME
So now for the gory details of how to actually make Sureal Time work. First we
need to look at players that are grouped, and isolated players. If a player is on a level with
no other players, there is no need to use anything other than turn-based movement. The
simple turn based movement is sufficient to cover this case, as it allows a player to play at
their own pace.
If there are two players on a level, it is more likely that they will need some sort of
movement control. When and where does this take place? If one player is on one side of the
level, and the other player is on the other side of the level, they are not going to interact
with each other much. So even though two players are on the same level, they may not need
to have movement control.
When is movement control needed? As two players get closer and closer, their
actions are going to start to effect each other. A player that zaps a wand or casts a spell
might effect the other player. So if we determine the largest area of affect for most events a
player can cause, a boundary is formed. If this boundary is 16 units, when a player is within
16 units to another player, both players now have some form of movement control. When
two players are further apart than this, they live in their own little turn-based world.
Now lets consider three players: A, B and C. If player A is within 16 units of
player B, and player B is within 16 units of player C, but player A and player C are outside
the 16 unit range, what happens? Simply all three players come under the same movement
control. This is a simple case.
Next, consider four players: A, B, C and D. What if player A and player B are
together, and player C and player D are together. However these two groups of players are
not within the same 16 units. It would not be fair to place all four players in the same
movement control, so two different "forms" of movement control are used.
Now we can bring this al together into a simple set of two rules:
Rule 1) A player that is outside a radius of 16 units of all other players on the same level is
placed in a turn based movement.
Rule 2) Players or groups of players that are within 16 units of another player or group of
players are placed in the same group. These groups are "controlled movement" groups.
The next aspect of Sureal Time is what happens to players that have movement
control? First of all, if no players in the controlled group move, nothing happens. This
means that players could talk to each other to determine what should happen next. Players
would be able to check their inventory for a particular item.
Rule 3) When groups are in controlled movement, if no players move, then no turns are
made in the game.
When a player makes a move, what determines how and when other players
move? The first part in answer to this question is related to the speed of the connection a
player has. A player with a fast connection would be able to make moves faster. A player
with a slow connection would make fewer moves. In addition to this aspect, players can
sometimes be "faster" in the game: intrinsic speed.
When several players are connected to a machine, the speed of a connection can be
obtained. Obviously the slowest connection is the best one to select for the speed of a group
of players, because it makes all movement fair on all players. If a player has an intrinsic
speed, all other players' base connection speed is modified to reflect this.
Rule 4) All players have a base connection speed. In a group of players, the slowest
connection speed is selected as the timeout basis for movement.
Rule 5) The base connection speed is only ever increased.
Rule 6) A player with an intrinsic of speed modifies the base connection speed of all other
players in a group.
So what happens if a player does not move at all, and another player close to them
moves? In this case the player that does not move has a certain amount of time to move
after the other player has moved. Once this time has ended, they will be forced to move.
This introduces a whole new problem, as to what moves are made when a player is forced
to move.
The moves that are forced by the computer are usually "intelligent". For example,
a player that is in combat will remain in combat unless they are badly injured or in need of
food badly. These rules are expanded in detail later. Once a player that is being forced to
move, and has made more than thirty moves, they are automatically saved.
In addition there is also the problem of a player that has lost their connection and
then enters into Sureal Time. If it is know that a player has lost their connection they are
automatically saved. Otherwise the player makes forced moves until they have exceeded
the thirty moves limit, and are saved by default.
Rule 7) After a player in a group makes a move, all other players must move within a
certain time.
Rule 8) Players that do no move within the time limit are forced to move, with the
computer making an intelligent move, such as attacking the last attacked monster (see
forced move rules).
Rule 9) If a player is forced to move more than 30 times in a row, they are automatically
saved.
Rule 10) If a player looses their connection, they are automatically saved.
Rule 11) A player can enter into Sureal Time even if they are not moving.
In some cases a lag in the connection between the client and server could cause a
players key-press to arrive at the server after a forced move has occurred. If the key-press
arrives within a certain amount of time after the forced move, it is ignored. This ignore time
can be set by the player.
Rule 12) After a forced move, all key-presses from the player forced to move will be
ignored for an amount of time specified by the user.
Additionally there is also a reaction time involved. This is considered a "fair" time
by which most players will see another player move, think of an appropriate move, and
make the move. This reaction time makes a player being forced to move slower than a
player moving by its self. Due to this slower speed, a player being forced to move has a
tally for forced moves to be made. All moves on this tally will be made unless the player
being forced to move presses a key to move.
Rule 13) A reaction time will be added to the time before a player is forced to move. The
reaction time should allow for a player to see a move, think of a move, and make it.
Rule 14) For every move that forces a move on another player, the player that is forced to
move will have a tally kept. This tally will be reduced every time the player is forced to
move. When it reaches zero no more forced moves will be made.
Rule 15) A player that makes a move will reduce their forced move tally to zero.
That appears to be most of the main parts of Sureal Time. There are some
additional problems that do begin to appear. For instance, what happens with monsters no
there is more than one player? As said earlier, monster AI has to be much better than
before, and able to cope with the problem where they might have three of four players
attacking them at once.
The solution is fairly simple. Every monster is "attached" to the monster that is
closest to them. In the case where two players are of equal distance, one of those players is
selected at random. Some people consider this to be unfair for the monster: If two players
are close (but not next to) a monster, both could attack it. However if you consider both
these players would more than likely be in Sureal Time, the monster would receive at least
as many moves as a forced move player would.
As two or more players get closer to a monster, it will become "unfair" for the monster.
Monster may need to be harder to kill, or attack in a group. This aspect of the game design
is left to the designer to decide. A combination of more monsters, monsters that attack in a
group, and smarter monsters is recommended.
Rule 16) Every monster is attached to the player they are closest to.
Rule 17) When the player a monster is attached to makes a move, the monster makes a
move.
These 17 rules are a fairly good summery of Sureal Time. In addition to these
rules, an appendix at the end includes a set of rules recommended for forced moves. It
seems fairly simple, however putting these rules into practice is tricky, as will be seen in
the example source code.
EXAMPLE SOURCE CODE
Before providing sources that implement Sureal Time, there are a few things to
say. To start with, this code only shows how the movement aspect of Sureal Time works.
Aspects such as the monster movement are left out. In addition, rule 12 of Sureal Time (key
presses ignored for a certain time) has not been delt with. This is viewed as a small addition
to the source code - something has to be left out to challenge people.
Writing Sureal Time code is not something to be undertaken lightly. The original
version of the source code was written in Java, and did not use millisecond timers. The
second version was in c/c++ and had a few bugs, and found a few problems in the original
implementation. What is provided here is the third version of Sureal Time. All up
development took about 20 hours.
Most of the source code is documented, however the algorithm basically follows
along the following lines:
1. Continue looping until input is received (from the keyboard). Simulates incoming data
from players. (This looping should be based on a sleep loop. The next event to occur is set
as the length of time to sleep. If no events are selected, sleep continuously until an input is
received).
2. If the key-press is 'Q' quite the program.
3. If the key-press is for a player, store the keypress (the player is no longer forced to
move).
4. If the sleep time has ended, check for forced moves. If there are forced moves, make
them.
5. If the sleep time has ended, make moves, and update the details of players. If other
players are on the timer that a player has just moved on, set the forced move timer for each
player.
The first file is the Sureal Time header file "sureal.h". Cut and paste this to a file.
The second file is "sureal.c" containing the main source for the algorithm. Again cut and
paste into a file. Compile this code with your preferred compiler: "cc -o sureal sureal.c"
Once this has been done, run the program with "sureal". When running, press 'Q'
and enter to quit. In the configuration below, press '2' then enter. This simulates a move by
player 2. There are three players in this example: 0, 1 and 2. 0 and 1 are on the same timer.
If you enter '0', player 1 will eventually be forced to move. To see more of what is
happening, recompile the source code: "cc -DDEBUG -o sureal sureal.c".
Now for a few quick hints and tips on how to modify the source code. First of all,
in most cases you should only need to modify the header file "sureal.h". NPLAYERS is the
number of players in the "game". If you increase this, do not forget to add another element
to the array of players created just below the NPLAYERS define. For each player created,
the first number is the id / timer the player is on. The last two numbers are the
seconds:milliseconds for the players timeout.
LEADWAY is what has been called in this document the "reaction time". The
greater this value, the longer period of time the player has to respond to a move made by
another player. A side effect of this is if a player is forced to move, it will take longer
before the forced move is made if LEADWAY is increased. MAXFORCED specifies the
number of moves before a player would be forced to quit. In the code below this has been
set to 10 so as to speed the results up.
The CSureal class is where all the important timers and numbers are kept track of.
Refer to the comments in the header file as to what each of these variables are. For most of
the rest of the source code in "sureal.c" please refer to the comments. It looks complicated
mainly because of the need for milli second timing.
The only thing to really take note of in the actual source code is the select() call
from the main function. This call has been used for two purposes. Firstly it allows
millisecond timing. Secondly, it can be combined with a socket setup such that connections
and data from the outside world are received here. Essentially by pressing a key the user is
simulating incoming data from a player.
My final comment is this: Do not just look at the sources. Try it out to see how it
works. Most likely some of you will have trouble of some sort. Please contact
bendchon@mehta.anu.edu.au and report any problems or bugs so this document
can be kept up to date and others have fewer problems.
-------------------------------------------------------------
#ifndef _sureal_h_
#define _sureal_h_
#include <sys/time.h>
#include <unistd.h>
// Redefine a few of the timer functions
#ifdef timerisset
#undef timerisset
#endif
#ifdef timercmp
#undef timercmp
#endif
#ifdef timerclear
#undef timerclear
#endif
#define timerisset(tvp)\
((tvp).tv_sec || (tvp).tv_usec)
#define timercmp(tvp, uvp, cmp)\
((tvp).tv_sec cmp (uvp).tv_sec ||\
(tvp).tv_sec == (uvp).tv_sec &&\
(tvp).tv_usec cmp (uvp).tv_usec)
#define timerclear(tvp)\
((tvp)->tv_sec = (tvp)->tv_usec = 0)
// Add a few timer functions
#define timershow(tvp)\
(tvp).tv_sec << "-" << (tvp).tv_usec
#define timeradd(tvp, uvp)\
{(tvp)->tv_sec += (uvp).tv_sec;\
(tvp)->tv_usec += (uvp).tv_usec;\
if ((tvp)->tv_usec > 1000000) {\
(tvp)->tv_usec -= 1000000;\
((tvp)->tv_sec)++; }; }
#define timersub(tvp, uvp)\
{(tvp)->tv_sec -= (uvp).tv_sec;\
(tvp)->tv_usec -= (uvp).tv_usec;\
if ((tvp)->tv_usec < 0) {\
(tvp)->tv_usec += 1000000;\
((tvp)->tv_sec)--; }; }
typedef struct timeval Timeval;
class CSureal {
public:
int key; // == 0 when no key has been pressed
int STTimer; // Timer player is associated with
Timeval STTimeout; // Timeout value (connection speed)
Timeval STNext; // When the next move can be made
Timeval STForced; // When the player is forced to move
int STForcedRemain; // Forced moves yet to be made
int STnForced; // Number of contiguous forced moves
CSureal(int a, Timeval b) {
key = 0; STTimer = a; STTimeout = b;
STnForced = 0; STForcedRemain = 0;
timerclear(&STNext); timerclear(&STForced); };
CSureal(int a, long b, long c) {
key = 0; STTimer = a;
STTimeout.tv_sec = b; STTimeout.tv_usec = c;
timerclear(&STNext); timerclear(&STForced);
STnForced = 0; STForcedRemain = 0; };
};
// This is just a list of sureal time class for simulation
#define NPLAYERS 3
CSureal list[NPLAYERS] = {
CSureal(1, 2, 0),
CSureal(1, 3, 0),
CSureal(2, 4, 0)
};
Timeval LEADWAY = {0, 500000};
#define MAXFORCED 10
// These are the functions for use in sureal time
Timeval * sleepTime();
void keyPressed(int, int);
void forcedMoves();
void makeMoves();
#endif
-------------------------------------------------------------
#include <sys/types.h>
#include <sys/time.h>
#include <iostream.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>
#include "sureal.h"
int main() {
srand(time(NULL));
while (1) {
// Sleep until the next action happens
#ifdef DEBUG
cout << "Sleeping\n";
#endif
fd_set rfds; FD_ZERO(&rfds); FD_SET(0, &rfds);
int retval;
retval = select(1, &rfds, NULL, NULL, sleepTime());
#ifdef DEBUG
cout << "Awake\n";
#endif
// Deal with any key presses
if (retval > 0) {
int c;
do {
c = cin.get();
if (c == 'Q') return 0;
if (c >= '0' && c <= ('0'+NPLAYERS-1))
keyPressed(c-'0',65);
} while (c != 10);
}
// Check for forced moves
forcedMoves();
// Make other moves
makeMoves();
}
return 0;
}
// sleepTime returns minimum time until next expected action
// it returns NULL when no action is expected
Timeval st;
Timeval * sleepTime() {
Timeval zt; timerclear(&zt);
Timeval ct; gettimeofday(&ct, NULL);
int stSet = 0;
timerclear(&st);
for (register int i = 0; i < NPLAYERS; i++) {
if (timercmp(list[i].STNext, ct, >) &&
(timercmp(list[i].STNext, st, <) || stSet == 0)) {
st = list[i].STNext;
stSet = 1;
}
if (timercmp(list[i].STForced, ct, >) &&
(timercmp(list[i].STForced, st, <)
|| stSet == 0)) {
st = list[i].STForced;
stSet = 1;
}
}
timersub(&st, ct);
#ifdef DEBUG
cout << "Sleeping for " << timershow(st) << endl;
#endif
if (timercmp(st, zt, <))
return NULL;
return &st;
}
// Player p has pressed key
void keyPressed(int p, int k) {
// if player already pressed a key, ignore this key press
if (list[p].key != 0) return;
// The player is no longer forced to move
timerclear(&(list[p].STForced));
// Store the keypress
list[p].key = k;
// Reset the contiguous count of forced moves
list[p].STnForced = 0;
// Reset the remaining forced moves to be made
list[p].STForcedRemain = 0;
Timeval ct; gettimeofday(&ct, NULL);
cout << "Player " << p << " pressed key "
<< timershow(ct) << endl;
}
// Force a player to move
void forcedMoves() {
Timeval ct; gettimeofday(&ct, NULL);
Timeval zt; timerclear(&zt);
for (register int i = 0; i < NPLAYERS; i++)
if (timercmp(list[i].STForced, ct, <) &&
timercmp(list[i].STForced, zt, !=)) {
// The player is no longer forced to make a move
timerclear(&(list[i].STForced));
// Player can move after their timeout finishes
timerclear(&(list[i].STNext));
timeradd(&(list[i].STNext), ct);
if (list[i].STTimer != i)
timeradd(&(list[i].STNext),
(list[list[i].STTimer].STTimeout))
else
for (register j = 0; j < NPLAYERS; j++)
if (j != i && list[j].STTimer == i) {
timeradd(&(list[i].STNext),
(list[list[i].STTimer].STTimeout))
break;
}
// Add one to count of contiguous forced moves
// If player more than MAXFORCED moves, they quit
if (list[i].STnForced++ > MAXFORCED)
cout << "Player " << I
<< " now forced to quit\n";
// Make sure no other forced moves to be made
cout << "Player " << i << " forced at "
<< timershow(ct) << endl;
list[i].STForcedRemain--;
if (list[i].STForcedRemain < 0)
list[i].STForcedRemain = 0;
if (list[i].STForcedRemain > 0) {
Timeval ft; gettimeofday(&ft, NULL);
timeradd(&ft,
list[list[i].STTimer].STTimeout);
timeradd(&ft, LEADWAY);
list[i].STForced = ft;
#ifdef DEBUG
cout << "Setting forced timer again for "
<< I << " to " << timershow(ft) << endl;
#endif
}
}
}
// Make moves if player has pressed key and timeout finished
void makeMoves() {
Timeval ct; gettimeofday(&ct, NULL);
Timeval zt; timerclear(&zt);
for (register int i = 0; i < NPLAYERS; i++)
if (list[i].key != 0
&& timercmp(list[i].STNext, ct, <=)) {
// The player is no longer forced to make a move
timerclear(&(list[i].STForced));
// Player can move after their timeout finishes
timerclear(&(list[i].STNext));
timeradd(&(list[i].STNext), ct);
if (list[i].STTimer != i)
timeradd(&(list[i].STNext),
(list[list[i].STTimer].STTimeout))
else
for (register j = 0; j < NPLAYERS; j++)
if (j != i && list[j].STTimer == i) {
timeradd(&(list[i].STNext),
(list[list[i].STTimer].STTimeout))
break;
}
cout << "Player " << i << " moved at "
<< timershow(ct) << endl;
list[i].key = 0;
// If other players on our timer, force them to
// move in the near future
for (register int j = 0; j < NPLAYERS; j++)
if (j != I &&
list[j].STTimer == list[i].STTimer &&
list[j].key == 0 &&
timercmp(list[j].STNext, ct, <)) {
if (list[j].STForcedRemain < 1) {
Timeval ft; gettimeofday(&ft,
NULL);
timeradd(&ft,
list[list[j].STTimer].STTimeout);
timeradd(&ft, LEADWAY);
list[j].STForced = ft;
}
list[j].STForcedRemain++;
#ifdef DEBUG
cout << "Setting forced timer for "
<< j << " to "
<< timershow(ft) << endl;
cout << "\tForced count: "
<< list[j].STForcedRemain
<< endl;
#endif
}
}
}
APPENDIX A - SUREAL TIME RULES
The following are all of the Sureal Time rules without any explanations:
Rule 1) A player that is outside a radius of 16 units of all other players on the same level is
placed in a turn based movement.
Rule 2) Players or groups of players that are within 16 units of another player or group of
players are placed in the same group. These groups are "controlled movement" groups.
Rule 3) When groups are in controlled movement, if no players move, then no turns are
made in the game.
Rule 4) All players have a base connection speed. In a group of players, the slowest
connection speed is selected as the timeout basis for movement.
Rule 5) The base connection speed is only ever increased.
Rule 6) A player with an intrinsic of speed modifies the base connection speed of all other
players in a group.
Rule 7) After a player in a group makes a move, all other players must move within a
certain time.
Rule 8) Players that do no move within the time limit are forced to move, with the
computer making an intelligent move, such as attacking the last attacked monster (see
forced move rules).
Rule 9) If a player is forced to move more than 30 times in a row, they are automatically
saved.
Rule 10) If a player looses their connection, they are automatically saved.
Rule 11) A player can enter into Sureal Time even if they are not moving.
Rule 12) After a forced move, all key-presses from the player forced to move will be
ignored for an amount of time specified by the user.
Rule 13) A reaction time will be added to the time before a player is forced to move. The
reaction time should allow for a player to see a move, think of a move, and make it.
Rule 14) For every move that forces a move on another player, the player that is forced to
move will have a tally kept. This tally will be reduced every time the player is forced to
move. When it reaches zero no more forced moves will be made.
Rule 15) A player that makes a move will reduce their forced move tally to zero.
Rule 16) Every monster is attached to the player they are closest to.
Rule 17) When the player a monster is attached to makes a move, the monster makes a
move.
APPENDIX B - FORCED MOVEMENT RULES
The following are a relatively "intelligent" set of rules to follow when a player is
forced to move. It is more than likely that other rules may need to be included. I would like
to hear comments on this section:
Rule 1) When no other rules apply, a player repeats their last action. A player that was
moving, continues to move, a player that was attacking, continues to attack.
Rule 2) It is not safe for a player to attack or move if they are hungry, or lacking hit points.
Rule 3) A player is lacking hit points if they have less than 10% or their total.
Rule 3) If a player is confused, stunned, or blind, they wait unless the opportunity exists to
attack safely.
Rule 4) A player that is not in attack mode, and is hungry eats.
Rule 5) A player that is almost fainting eats.
Rule 6) If a moving player comes to a door they open it (open, lock pick, keys, kick).
Rule 7) If a moving player comes to a dead end, they search for 15 units of time until
something changes. If nothing changes, they player resumes in the opposite direction.
Rule 8) If something changes while searching the player continues in that direction.
Rule 9) A player that can not move left, goes forward. A player that can not move forward,
moves right. A player than can not move right turns around and goes back the way they
came.
Rule 10) If a moving player enters a room, they will seek out the best items from any
objects.
Rule 11) A moving player will try to remain in Sureal Time, following other players.
Rule 12) If a player sees a monster it will attack at long distance first (throwing weapons,
potions, zapping known wands).
Rule 13) While in close attack, monsters will use weapons, spells, wands etc. The method
of attack selected is that which is considered best for the situation. In most cases weapon
based attack should be selected as the best method. However a wizard with 10% failure rate
on magic missile may opt to use that spell.
Rule 14) Players forced to move will not use objects being carried unless for offensive or
defensive purposes. If an object is unknown, it will not be used.
|