Question about game programming (and perhaps more general problems)...

Question

5.00/5 (2 votes)

See more:

Hi all,
I have a question on game programming. I am not a game programmer myself (and in fact I was never very interested in most of it), but I do have a question.
Of course I would Google it, but I can't seem to find what I'm looking for (and that's actually the problem, I don't know what I'm looking for).

So suppose you have a game and you enter a location, let's say a room. In this room are probably a few characters, perhaps even playable characters that might join your party!
So the first time you get into the room your character has a chat with some of the characters in the room.
After that it's time to go on a mission. If you go back to the room now the people there will say something like "What's up?".

Now you complete your mission and go back to that room. This time you will have a chat and a character joins your party! Now if the game progresses and you get back in the room the remaining characters will say "Long time no see."

So here's the actual question.
How does the game 'know' / 'remember' / store the fact that you've:
A) Never been in the room before.
B) Been there before, but haven't finished your mission.
C) Been there before, but not after finishing the mission.
D) Been there before and having recruited the character.

To me that sounds like a few boolean flags and a bunch of if-statements... Except a game of reasonable size (I'm thinking particulary of Final Fantasy games since they're my favourite and I just finished IX) has thousands, if not ten-thousands, of those conditions. Have you talked to person X, have you picked up item Y, have you visited location Z, etc.

And more recent games provide entirely different gameplay based on some actions you have or haven't undertaken.

Surely there is some common concept to deal with that kind of branching logic?
I can't seem to find it, but I can't imagine the source code of a game consists for 90% of if-statements either :)

Thanks!

Posted 17-Jun-14 9:03am

Sander Rossel

Add a Solution

Comments

Sergey Alexandrovich Kryukov 17-Jun-14 15:29pm

The question looks rather naive, but you raise a valid concern and quite reasonably formulate the problem; I voted 5.
The code consisting of 90% of "if" is just wrong code, you should not follow such brainless style. Your way of posting a naive question is quite productive, for a beginner: this is the sure way to really good engineering.

Please consider my advice in Solution 1 and read the referenced article for an example. It will eliminate all stupid "ifs" and "thens", will leave only the reasonable ones. :-) Your follow-up questions will be welcome.

Wish you the best of luck.
—SA

Sander Rossel 17-Jun-14 16:09pm

Thanks Sergey. A naive question is often an understandable question. And everyone understands non-technical talk.
Posting my train of thought and questions that arise from it probably gives me better answers than to type some technical words, like state machine, that I don't fully understand.
It might get the reader on the wrong foot and I won't get the answer I'm looking for.

I'm not so sure if I'm happy with being called a beginner though.
Well, in game-development I guess I'm not even beginning, let alone beginner :-)

I've already posted a follow-up question. I hope to get to the bottom of this (this state business is already very interesting and I might know where to successfully apply it in my every day job).

Sergey Alexandrovich Kryukov 17-Jun-14 17:18pm

You are welcome. We are all beginners, in one field or another, unless we stop moving forward. Sorry if you feel unhappy about by statements about beginning, I hope you did not consider as anything negative. Apparently, there are fields where you are a beginner (be it games, FSM or anything), as well as I am, and everyone who moves forward.

I hope you will find my answer useful and consider accepting it formally (green "Accept" button).

—SA

3 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Sergey Alexandrovich Kryukov · Accepted Answer · 2014-06-17T09:22:00

Solution 1

You are right; this is a more general thing: how to make common mathematical conceptions, structures/algorithms and design patterns in general programming and apply the same ideas to different projects; how to identify that the problem requires applications of some common patterns, structures, etc.

The bunch of problems you pose (quite reasonably, I think) is reduced to one such concept, well-known one: finite-state machines (FSM). Please see: http://en.wikipedia.org/wiki/Finite-state_machine[^].

In one of my articles (recently updated), I pointed out that a FSM can be represented as the mathematical relationship, which can be defined as any subset of a Cartesian square based on a finite set of elements considered as states: 3.6 Cartesian Square[^].

See also:
http://en.wikipedia.org/wiki/Cartesian_square[^],
http://en.wikipedia.org/wiki/Finite_set[^].

You can directly use it for implementation of your FSM, as this is the representation very convenient for implementation in code.

—SA

Posted 17-Jun-14 9:22am

Sergey Alexandrovich Kryukov

Updated 17-Jun-14 9:32am

v5

Comments

Sander Rossel 17-Jun-14 15:59pm

Hi Sergey, thanks for your answer. It just so happens I read something about the FSM (and some other state machines), but didn't see how they would solve the problem.
Let's take my example. Would it be correct to say the game has the following states:
1. Pre-mission, pre-enter room state.
2. Pre-mission, post-enter room state.
3. Mission state (this is probably a part in the game where you can't even get to the room).
4. Post-mission, pre-enter room state.
5. Post-mission, post-enter room state.

Or would the following be more suitable?
1. Pre-mission state.
3. Mission state (this is probably a part in the game where you can't even get to the room).
3. Post-mission state.
Where the fact if you have entered the room at least once is stored in a flag in the Pre- and Post-mission states? A scene is triggered using a regular if-statement.

That basically eliminates the need to keep a flag if you have completed the mission (which will probably save a lot of if-statements, for example for every reaction of the people in the room).
On top of that many flags can be contained in a state (where the flag makes sense), rather than as some global variable. For example the enteredRoom flag is meaningless in the Mission state.

But that still leaves a lot of room for variables that can't be tracked by state.
For example, suppose there is a chest in the room. You can open it before the mission and the chest will still be open after the mission (so it's basically a variable that travels with states, or perhaps is state-less). Would this still be some global variable and a piece of code at Room_Load() { if (chestOpened) { DrawChestOpen(); } else { DrawChestClosed(); } or some such?

Sergey Alexandrovich Kryukov 17-Jun-14 17:36pm

Okay, now you have some set of states. You know better which set of states will be more adequate for one approach and another. But here is how you use the FSM approach instead of just having flags (which also can be considered). If you build a Cartesian square on the set of states, each cell of this new set will represent two states: input and output. In a pure mathematical FSM, the content of each cell is just Boolean, it would indicate if the direct transition between input and output state is allowed or not. Say, if this is represented as the array of rank 2 (it's recommended to have this representation (possibly as redundant one) even if you base representation is different), you just index the cell with two indices: input and output states as indices.

In practice, the cell can contain some more essential information: for example, for an allowed transition, it could contain a delegate or method pointer which points to the method to be called to do the transition, with update of the UI or not; or it could be some data element needed to perform the transition. Even the cells representing the prohibited transition could be used. In one of my works, for example, I used to store the format of error message to be shown in case of the attempt to make a prohibited transition; it was used at the stages of debugging.

Actually, you are touching the problem of just having the state itself a complex object. Let's say, the behavior depends on the set of objects in possession. (The state of the chest also can be considered as "possession".) You can ether include the set of possessed object in the state, but then the total number of states grows fast with each object (due to having many combinations), and the number of transitions grows quadratically of the number of states. Then you need to think of something else. You can include only the basic states to the FSM (not objects). Objects will be some collections, possibly indexed by the states. In this case, those cells in the state machine won't have constant false or true values (allowed/prohibited); they can include the function which calculates the "prohibitiveness" of the transition depending on some arguments, one of such arguments can be the set of possessed object. Still, this will be far from hard-coded spaghetti-style "if" logic.

I hope it will give you some ideas. Any arguments? other concerns?

—SA

Sander Rossel 18-Jun-14 11:49am

I think I pretty much get the point (although writing something like that is a complete different matter) :-)
Thanks again for your help. It is very much appreciated.

PIEBALDconsult · Accepted Answer · 2014-06-17T09:46:00

Solution 2

"that kind of branching logic" "I can't imagine the source code of a game consists for 90% of if-statements"

Correct. Some very simple games (like ones I've written) can be done like that, but not the type you describe.

But think toward Object Oriented Programming...

Let's say there is a trunk, a trunk can hold something, it can be opened and closed, it can be locked or unlocked -- think about states and actions.
A character finds the trunk. Check trunk.State -- Locked. Iterate collection of loot, seeking a Key, find a Key. Call trunk.Unlock(KEY) -- Success. trunkState is now Closed. Call trunk.Open -- Open.
Iterate loot in trunk, remove what you want, add it to your collection of loot.
Ogre walks in. Iterate collection of loot, seeking Weapons. Select weapon. While character.IsAlive and ogre.IsAlive call weapon.Attack ( ogre )

That, coupled with a way to persist the state of everything, is the way to go.

Posted 17-Jun-14 9:46am

PIEBALDconsult

Comments

Sander Rossel 17-Jun-14 16:22pm

Have you read Sergey's answer and my follow-up question? Is that the kind of state (machine) you're talking about?
So suppose I have a magical chest and the only way to open it is by telling it the magic word. The only way of knowing the magic word is by talking to some guy at the other end of the world. The magic word isn't something in my loot that I can iterate through. The only way of knowing if I talked to that guy is probably some flag somewhere, right?
So wouldn't you get something like:
if (talkedToMagicWordGuyFlag)
{
trunk.Open();
}
?

Perhaps I'm very stuck in thinking in if-statements...

Paulo Zemek 17-Jun-14 17:31pm

Note that actually there are game-wide information, mission specific information or something-else specific information.

For example, during a mission, some data may be stored regarding the character and others that he talked to or about items he had touched. As soon as the mission ends, all that info may be lost.

Booleans? Well... you can use a hashset of strings (not the best, but only to exemplify) and store all the data that may be of "interest" to the mission. Things like:
"TouchedTheMagicCat", "KilledADragon", "KilledTheDragon"... or anything else. Note that all of those could be boolean variables inside a single class, but by using a hashset you never need to have a class with all the possibilities (and so, if the missions may be loaded from xml files, the "needed items" may be searched by names instead of counting on an existing field).

Then, we return to the idea: Each npc (or room, if each action is by room) may look for specific traits in the current character mission... or in the current character itself (like the character level). And anything can be stored if it is important for the game (number of kills the character did, number of times the character died and was revived... even the number of saves done in the game...).

Paulo Zemek · Accepted Answer · 2014-06-17T09:52:00

Solution 3

Actually there are many ways to do that, but let's split things:

1 - Where are the things stored?
Maybe into a database. Maybe in memory. Maybe on a text file.
Actually, if the game is multiplayer there are big chances that a database is used. If not, it is probably stored in a file (be it binary or text).
It can actually store any "combination" of information needed by the game. For example: You talked to person X, when you were at level 1, before mission Y. You talket to person Z, when you were at level 3, after mission 5... or anything that's valid for the game.

2 - Actually each character that you encounter may have its own rules attached. It is even possible that those rules are stored in an XML file but that's not what's important. Those can be things like:
* Have ever recruited another character?
* Is level X?
* Has already talked to "me"?

And, if you look... independently on how many characters exist in the game, each character will have only a limited set of rules.

It would be pretty simple to have a table that "binds" different player characters to different non player characters and stores values like "time of that conversation", purpose of the player character at that moment and similar... and then the next time you encounter that "person" it looks that it was 3 months ago that you talked to him and says "wow... I though I would never see you again".

Posted 17-Jun-14 9:52am

Paulo Zemek

Comments

Sander Rossel 17-Jun-14 16:33pm

Hi Paulo, thanks for your answer.
Let's take your advice into my example.
I would have a Room object which has some rules: VisitedAtLeastOnceBeforeMission and VisitedAtLeastOnceAfterMission?
So my character enters the room and the code goes:

if (!???.MissionCompleted && !room.VisitedAtLeastOnceBeforeMission)
{ scene... }
else if (???.MissionCompleted && !room.VisitedAtLeastOnceBeforeMission)
{ scene... }
else { ... }

perhaps 'room' can be replaced by 'this' if the code is running in the Room object.
That can't be right.
VisitedAtLeastOnceBefore/AfterMission could be stored in the Room object (perhaps in different states, like Sergey suggested), but where would the MissionCompleted come from? The player Object perhaps?.

Am I understanding you correctly?

Paulo Zemek 17-Jun-14 16:50pm

Think differently.
When a character talks to someone (in this case, enters the room and there's a person interested in talking to you).
That person may be programmed like:
Check when it last talked to you (this will look into the database to see if there's a registry binding that player character to this npc character).
If there is not:
Hi. Are you new here?

If there is. Then, it looks:
Was that character in a mission last time it was here?
Is it in a mission now?
Is it the same?

Those conditions may yield results like:
Do you need any help with your current mission?
How did your last mission end?
Hey... I see that you are in a new mission. Needing new items?

So, that character has many "conversation paths". It only needs to look for information about the currect character talking to him, and it can use the database to have "memory".

Paulo Zemek 17-Jun-14 16:52pm

In fact, it is important to note that the state is not in the player character or in the room/npc (except if it is a single player game). It is in the combination of both.
In the database, it would look like:
PauloZemek/FirstItemSeller (the key) -> anything else. The information needed by the game.
So, another character will have its own key (SomeOtherUser/FirstItemSeller)... and other sellers/persons that you talk on the game will also have their own.

Sander Rossel 18-Jun-14 11:54am

Thanks for the comments Paulo. With all the answers and comments combined I think I'm getting an idea of how you could solve such problems :-)
Your help is much appreciated.

Question about game programming (and perhaps more general problems)...

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

Question about game programming (and perhaps more general problems)...

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

Existing Members

...or Join us