Sign in to follow this  
Los Frijoles

Code Efficiency

Recommended Posts

I haven't posted here in a while, but I am posting this in multiple places so I can get the most ideas. This is written in C++, but if you do not know C++ you should still be able to help since this is an algorithm problem, not a scripting problem. Basically, I am making a Settlers of Catan clone and I am writing a collection of classes for storing and accessing the data for the 19 hexagonal tiles. So far I have it so each point, line, and hex is indexed by a number unique to that tile, point, or line (not unique to the whole scope of things, just to the shape of the item e.g. point 0 on hex 0 is in line 0). Everything is interconnected and references to everything else. This interconnectivity ensures maximum efficiency when accessing statistical information on the tiles. (e.g. I can ask for statistics on hexes on a point or points on a hex without having to look through index tables and such) Things were progressing well in writing all this until I realized that I had linked up the points to the hexes in code (the points had pointers to the hexes) but the hexes were not linked to the points in code (the hexes need to have pointers to the points). This was very frustrating since I had already written the code for 54 points linking to multiple hexes per point (coming up to about 300 lines in that one function) and still needed code for the lines to hexes. My question is, what is the most efficient way to link the hexes back to the points? Surely there is a better way than adding an extra line of code beneath every single other existing line? Here is my code: http://cuznersoft.com/Hex_storage.h

Share this post


Link to post
Share on other sites
I'm not familiar with Settlers of Catan, so I can't say whether this is the most efficient way to store these connections or if you really even need all of these connections. Why is it not enough just to know that you have a "hex", and the hex is connected to the following hexes? Assuming you do need all of this information, you might consider storing it outside of your code. Put it in a file and then just build a parser that can read the file and create all of the connections. You are bound to make some mistakes with so many connections, so this will make it much faster to build and test since you won't have to recompile every time you make a change.

Share this post


Link to post
Share on other sites
Quote:
Original post by Los Frijoles
I haven't posted here in a while, but I am posting this in multiple places so I can get the most ideas. This is written in C++, but if you do not know C++ you should still be able to help since this is an algorithm problem, not a scripting problem.

Basically, I am making a Settlers of Catan clone and I am writing a collection of classes for storing and accessing the data for the 19 hexagonal tiles. So far I have it so each point, line, and hex is indexed by a number unique to that tile, point, or line (not unique to the whole scope of things, just to the shape of the item e.g. point 0 on hex 0 is in line 0). Everything is interconnected and references to everything else. This interconnectivity ensures maximum efficiency when accessing statistical information on the tiles. (e.g. I can ask for statistics on hexes on a point or points on a hex without having to look through index tables and such)

Things were progressing well in writing all this until I realized that I had linked up the points to the hexes in code (the points had pointers to the hexes) but the hexes were not linked to the points in code (the hexes need to have pointers to the points). This was very frustrating since I had already written the code for 54 points linking to multiple hexes per point (coming up to about 300 lines in that one function) and still needed code for the lines to hexes.

My question is, what is the most efficient way to link the hexes back to the points? Surely there is a better way than adding an extra line of code beneath every single other existing line?

Here is my code: http://cuznersoft.com/Hex_storage.h


Some random comments...

- a 300 lines function is bad by itself IMO. keeping a 100 lines max is healthy.

- when doing this kind of analysis, always think about cache coherency. Data that will be accessed at the same time should be contiguous in memory.

Share this post


Link to post
Share on other sites
Quote:
This interconnectivity ensures maximum efficiency when accessing statistical information on the tiles. (e.g. I can ask for statistics on hexes on a point or points on a hex without having to look through index tables and such)


Why do you care about this efficiency? The user cannot possibly notice the difference. Settlers is turn-based anyway.

Share this post


Link to post
Share on other sites
But, to answer your actual question, I would write a function that does this:


void hexLinker (Hex& someHex, std::vector<Point*> allPoints) {
unsigned int numPoints = allPoints.size();
for (unsigned int i = 0; i < numPoints; ++i) {
if (allPoints[i]->isLinkedTo(someHex)) someHex.makeLink(allPoints[i]);
}
}


and run it on each Hex in succession.

Share this post


Link to post
Share on other sites
I built a parser since it seemed like the best idea so far. It worked wonderfully and I think I will stick with that. I had never used the fstream functions before, but they seem pretty straightforward and simple.

@King of Men: I care because I do not want to type a 500 line function and because this file will be inside a DLL and each function has less that 1/30th of a second to execute before the user will notice a slight jump in the framerate.

Share this post


Link to post
Share on other sites
I think the point King of Men is trying to make is that in 1/30th of a second computers can move a zillion polygons, draw a brazillian texels and perform nine gadrillion AI calculations. 19 hexes? Really not going to be a problem. Unless you have actually observed such a problem for yourself already?

Furthermore, even if it happens, the user might notice a switch from 30Hz to 20Hz in a fast-paced first person shooter, but in a turn-based board game? It's very likely that they won't.

Share this post


Link to post
Share on other sites
Quote:
Original post by Los Frijoles
I built a parser since it seemed like the best idea so far. It worked wonderfully and I think I will stick with that. I had never used the fstream functions before, but they seem pretty straightforward and simple.

@King of Men: I care because I do not want to type a 500 line function and because this file will be inside a DLL and each function has less that 1/30th of a second to execute before the user will notice a slight jump in the framerate.


I've looked over your problem and the original game, but I couldn't find out what the point and line are, or what the relation between them an hexes is, so I can't offer an advice to that.

But as for performance - why do you need to update this 30 times a second? If anything, then that is your performance problem. Since this is turn based, you should be updating the information more than once every turn, which will depend on player's input only, so likely once every 5 to 60 seconds.

Keep in mind, that adding so many links increases the memory requirements just enough to make the data not fit into L1 cache. In this case, calculating statistics will likely run slower with pointers, than it would with direct index calculation, where the entire board would fit into the cache.

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