Sign in to follow this  
Daragoth

Using Lookup Tables

Recommended Posts

Daragoth    100
I'm programming a game in MSVC++10 and was wondering what would be the best method of implementing a constant lookup table with the data known at compile time. This table will hold information regarding skills used by characters (around 200 or so), for example:
ID		Name		Power	Type		Effect		MP
FIREBALL	"Fireball"	50	FIRE		BURN		12
LIGHTNING	"Lightning"	75	ELECTRIC	NOEFFECT	14
BLAZE		"Blaze"		100	FIRE		BURN		25
HYPNOTIZE	"Hypnotize"	0	TIME		SLEEP		10
...
(etc.)
The ID column holds a unique enum value I use throughout my code to refer to the specific skill. The name is a string representation of the skill, used for output. Power is an integer used for damage calculations. Effect is another enum value I use to refer to the effects a skill can generate; since some skills have the same effect, it is easier to have a seperate effect value rather then refering to the effect via the ID, in addition to giving me greater flexibility. Finally the MP column is an integer value used to refer to the skill's MP cost. The most important thing is that the implementation is fast. This is because the AI I'm using for my game simulates all possible move selections it can make every time it gets a turn, and uses the move that gives the highest possible chance of victory. Because the number of simulations grows exponentially, each one needs to execute very fast. So at every point while programming the game I am always trying to optimize for speed. The ID of the skill will always be known when retrieving information (in other words it will never be necessary to get all skill IDs that have the 'BURN' effect), so I would think storing it as an array of structs with the index being the ID of the skill would be the fastest implementation (memory usage isn't a big concern). The next most important thing is that the data is able to be easily viewed and edited. My current implementation is to use functions that have large switch statements within them and return a value based off the skill ID passed to it. But I am unsure of the speed of this, and would also prefer an implementation where I can view the data all in one concise table, like the one I posted above. If my previous guess that storing the skills as an array of structs was correct, then I guess my question is if there is a way to transform a table into this data structure at compile time in MSVC++10? I appreciate the help, thanks.

Share this post


Link to post
Share on other sites
LessBread    1415
A structure and an array fits your needs.


struct Skill {
char *Name;
int Power;
int Type;
int Effect;
int MP;
}

struct Skill skills[] = {
{ "Fireball", 50, FIRE, BURN, 12 },
{ "Lightning", 75, ELECTRIC, NOEFFECT, 14 },
{ "Blaze", 100, FIRE, BURN, 25 },
{ "Hypnotize", 0, TIME, SLEEP, 10 } };



Put that declaration into the relevant source file, use extern in a header file if you need to access it in other source files. Use enums for fire, burn, electric etc. Create the enum for HYPNOTIZE, BLAZE, LIGHTNING, FIREBALL etc. starting with 0 so that you can use the ID as the index into the array. If for some reason you need to start the enum with a number other than 0, subtract the starting number from each ID so that you can use the difference as the index into the array.

Share this post


Link to post
Share on other sites
frob    44903
What you have will work. It is not extensible, but it will work.


To allow it to grow, that file needs to be outside the game. It needs to be kept in data.

You can easily keep this sort of thing in a simple data file. Some people prefer "flat files", just simple raw data. Other people prefer to stick it in XML or something that can be read by data. Either is fine.

Then you load it up in your game.

As a side benefit, you could easily add an in-game command to RELOAD the file, allowing you to make changes and see them instantly.


The actual time it takes to look it up will likely be small, unless you have a few hundred of them. A std::vector of your struct would be good because they are all sequential, which can help make your cache happy. For a short table it will only take a few nanoseconds to iterate over the entire list. If you still want faster access, sort it and use a binary search, and you will get O(log n) lookup time. Unless your list is big, neither will show up as a blip on your performance.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this