# How can I have my game engine track player history?

I'm in the very early stages of designing a browser-based text RPG. The project is basically just something I'm doing for fun and as a learning experience. I'm starting to wrap my head around the infrastructure of the game and I keep getting hung up on the best way to accomplish this.

If I have a map comprised of a grid with different items/monsters/quests/etc. in each 'tile', what's the best way to keep track of the areas on the grid where the player has been?

If the map is a grid of 1000x1000 squares, I want to know that in the player's entire gaming history, they have already visited squares A-1, F-6, GQ-46, etc. This list could be huge for each and every player.

Along the same lines, if I have quest-dependant events, how do I track the quests players have completed? Each player would need to have something letting the engine know if they have or have not completed potentially hundreds of quests.

My first idea was to save this information somehow in each player entry in the database, but that would mean a field for every one of the tiles in the 1000x1000 map. That doesn't seem like it would scale.

I'm just not sure how to store the info that lets the engine say "hey, I know that out of all the tiles on the map, this player has been on this particular one before." or "out of all the quests, this player has completed this particular one".

What is the best way to approach this?

• You need a good book on relational databases and SQL; it's clear you don't know how to use them. Sorry to be so blunt about it. To represent the relationship between players and the tiles they've visited, you would have a table like player_tiles, with two columns, player_id and tile. For each title a player visits, you insert one row. You'd have a similar table relating players to quests they've completed. That is the minimal representation of the information you need to store. – Dan Grossman Jul 16 '11 at 4:03
• Dan - that's a fantastic way to approach it. I have used that concept before once or twice but didn't think to use it here. And no, I'm not an expert with databases - that's why I am doing this, to learn. And look, thanks to you, I already learned something :) – Cail Jul 16 '11 at 10:43
• @Cail - I don't think that Dan's idea is quite something you'd want to use for a game. Especially if you're actually going to have a map thats 1000x1000 or more. Consider that if each player walked over every tile, you would have 100 000 records for EACH player in that table. Not only that, but I'm assuming you'd want to use that data somehow in your game which means looping through all records for each player. It may work fine initially, but I don't think it will scale well. On the other hand, using the method outlined by Patrick (using a bit-map) might be more efficient/effective for you. – Richard Marskell - Drackir Sep 14 '11 at 21:17

## 3 Answers

Since your map is a grid of fixed size and all you want is "has been visited", for the first part you can use a bit-map. For a 1024x1024 grid your storage size would be 128K and very fast to look up and small enough to keep in memory if you need super fast access (for fog of war rendering, or info overlays).

The quest info could be done two ways. It would be pretty easy to store them in a database and run queries as needed, and probably the best solution overall, @Dan Grossman

The other method would be to generate a hash from the quest information then simply store a list of hashes that the player has completed. Storage would grow dynamically, hash lookup at run time is very fast, and new quests could be added whenever you wanted.

• +1 I really like that bit-map idea. I think I may use it in my game. – Richard Marskell - Drackir Sep 14 '11 at 21:18
• @RichardMarskell-Drackir you should read up on adjacency matrices, they will give you some idea on implementation. (Also see stackoverflow.com/a/5419933/431528) – deceleratedcaviar Jan 23 '12 at 7:55

A database seems like overkill. As @Patrick Hughes says, a bitmap is a great choice for map coverage plus 'fog of war' implementations. Bitmaps can also be used to track true/false conditions of game story. For example, you might have a list of ids or an enum that map to game events, like

enum GameEvents {
VisitedTheTown = 1,
KilledTheOgre,
SavedThePrincess
}


Then you can do BitMap.Set(GameEvents.KilledTheOgre); when that action happens, and you can query for it later if some dialog tree depends on it. It's also efficient to store in your save game since it's only 1 bit for every yes/no game event state. You just don't want to be adding/removing items from the middle of your enum if you want different versions of your saves to be compatible.

Another approach is to use a data structure called a Blackboard. Implementation is up to you but it's often like a cross between a property bag and the Windows registry. You can store yes/no conditions like in a bitmap but you can also store strings or quantities (for the ever popular "Kill 10 kobolds" quest).

Here's a link:

http://aigamedev.com/open/article/static-blackboard/

And a book that mentions the subject:

AI Game Programming Wisdom

• It would not be a 'bit map' as such if you can store more than... well, a bit in each field. But the idea remains, as many solutions will probably store a byte for each field anyway, you can store a lot of information in those 8 bits :). – deceleratedcaviar Jan 23 '12 at 7:53
• @Daniel, it's exactly a bit map: if bit 1 is set, VisitedTheTown is true, if bit 2 is set, KilledTheOgre is true. Unset bits are false conditions. In a map sense, a set bit might be an explored tile or sector. Storing quantities requires a different data structure as I said. – Chronic Game Programmer Mar 21 '12 at 18:36

A database is an excellent tool for something like this, storing it in any other way would force you to (partially) recreate what a database already solves for you. As was mentioned by Dan in comments, using a relational table that maps the players id to the cell id that has been visited is a good solution. Databases are built for just this sort of thing and querying it for if a cell has been visited is a fast operation.

If database storage is costly for you (which it might be on a hosted solution) you can consider compressing the number of fields somewhat. In the case of "has this cell been visited" you would normally be forced to travel through the areas sequentially, so to get from A1 to A3 you would have to pass through A2 (or go a path around A2 depending on terrain).

You can use this fact by storing strips into the database instead of each cell individually, for instance (player, row, firstHorizontal, lastHorizontal), this way you can find out if a player has been in a cell by:

select * from VisitedAreas where player=@playerID and row=@row and firstHorizontal<=@column and lastHorizontal>=@column


The update method would be more complicated in this case however, you would have to look for a strip that is next to the current cell and if one is found, update either first or lastHorizontal field as appropriate, or if one isn't found you add a new strip where first and lastHorizontal is the current location.

Quests can be solved in a similar way, (playerID, questID, progress), progress can either be a foreign key to a "QuestSteps" table or you could go the oblivion/skyrim approach and store a number from 0 to 100 for every quest that maps to what you have done so far, for instance:

10 - accepted quest
11 - killed 1 goblin
12 - killed 2 goblins
15 - found the necklace in the chest
20 - returned necklace
30 - discovered the necklace wasn't the questgivers
40 - killed the questgiver and retrieved the necklace
100 - returned the necklace to the goblin owner


Again, if you wish to reduce the number of fields per player you can lump quests together by area, in many cases the player would probably finish all quests in a region before moving on to the next. In this case you can have a RegionCompleted (playerID, regionID), while a player is working on the quests in a region this is blank and you check the "QuestCompetions" (playerID, questID, progress) table for each individual quest, once all quest are completed however you add a row to the "RegionCompleted" table to mark this, and then remove the rows that correspond to that region from the "QuestCompletions".

Hope this helps.