64mb data struct vs bad algorithm

I got it because my linkedlist class is 16 bytes. I have 3 pointers (head, tail, current) and an int (number of nodes). That makes 128*128*128*16=32mb... hmmm. I think there is a problem with my math. I think I got 32 bits and 32 bytes confused in my math the first time... Anyway, 32mb is still far too much (and 128^3 isn''t even that big a galaxy. I want it to take several days real time to cross the galaxy.)


--------------------


You are not a real programmer until you end all your sentences with semicolons; (c) 2000 ROAD Programming

You are unique. Just like everybody else.

Yanroy@usa.com

Visit the ROAD Programming Website for more programming help.

I see your point, and I even considered it, but the pointers can''t be NULL because something may want to fly there some day. Once it gets there, if it doesn''t exist it could create a new node, but then the memory usage goes through the roof as the galaxy is explored. One other thing about the comparing algorithm: I would only check it every time a ship moves, for the ship that moves (not everyone always).

--------------------


You are not a real programmer until you end all your sentences with semicolons; (c) 2000 ROAD Programming

You are unique. Just like everybody else.

Yanroy@usa.com

Visit the ROAD Programming Website for more programming help.

Maybe something like Dynamic Loading would help.... You save the the galaxy to disk and load it when needed, so in your linkedlist you could save a path to a file or a unsigned int for the number you associate with the galaxy part.... I don''t know how fast this will work though (depends on how fast the current galaxy setup could change) and your galaxy would be limited to Harddisk size, well almost ;o)

I don''t know if this might have helped, if you need some more infos just mail me...
cya,
Phil

Visit Rarebyte!
and no!, there are NO kangaroos in Austria (I got this questions a few times over in the states ;)

Have you thought about using an octree?

The overly simple explanation:
Divide the galaxy up into 8 sub-cubes.

For each sub-cube, if it is empty, or it is "small enough" stop. Otherwise, recurse into each subcube.

With that much data, you must look into using database methods. Yes, they''re slow. That''s why God made loading screens. Keep that data on disk, dynamically load it into memory from the database when you need to.

I have considered an octree. I was thinking about the problem that arises when the ship is close enough to the edge of a sub-cube that its sensor range extends into the next cube. That sort of defeats the purpose. I think I will go with the coord-comparing algorithm and hope that it isn''t as bad as I suspect it will be. I may need to put a cap on the number of players or other celestial bodies.... Using just plain coords will also allow for better simulation of warp speeds...

Stoffel: Have you ever played an online game that says ''loading'' every time you do a hyper-jump with you ship? That would be horrible, especially if it took a long time. I may have forgotten to add (I hope it doesn''t matter too much) that this is a text-only (with colored text) game. If you have ever played Seth Able''s Planets: The Exploration Of Space, my game is similar, but with many MUD aspects thrown in (mainly the interface).

--------------------


You are not a real programmer until you end all your sentences with semicolons; (c) 2000 ROAD Programming

You are unique. Just like everybody else.

Yanroy@usa.com

Visit the ROAD Programming Website for more programming help.

Oh good god, loading the data for a text game would take no time at all.

And mmorpgs have lots of "Loading, Please Wait..."


The tree & search is the way to go. You search your cube and all the adject ones - or the ones within range (that prevents the border problem you mentioned). So you should break it down at least twice (recursively) otherwise it saves you no calc time.

I''m not sure why you have make an array at all?

Lets say you wanted to do it in 2D instead - the generalization to 3D should be apparent. Why don''t you include a sector data member in the classes for your players, star systems, NPCs?

class objectInGame {
....
// data members
SECTOR sector; // sector is a 4-vector of ints for a 256x256 playfield
};

Now, take your whole playing 256x256 playfield and divide it into quarters. Number each subfield by 1 to 4. Then divide each of those quarters into quarters. And then keep subdividing until you get down to 1x1 tile. You can now discribe the location(sector) of any object by 4-vector with each member being 1,...,4.

The only part I haven''t completely thought through is what type of data structure you want to use to store the objects in. You obviously want something like a binary tree but with each node having four subnodes. You also don''t want to have an actual node in the tree unless you have object present in the sector that that node represents. Err.. is that a quad tree?

Sounds too complicated, ... sheesh, try this instead...

Try to use some kind of hashed list except that your "key" to looking up objects in the list would be a four-vector like (1,2,2,1) specifying which subrectangles to pick. In each of the nodes you wouldn''t store the actual objects, rather a linked list that contains pointers the objects that are currently in that sector

class node {
linkedList listOfObjectsInThisSector; // store pointers to the objects that are currently in this sector
};

In either case, I hope you see that finding the nearest sectors to yours shouldn''t be that much of a problem. From any lookup "key" (a,b,c,d) you should easily be able to find its four(eight?) closest neighbours and search their linked lists for drawable objects.

Hope this helps!

PS. hrmm... the hash table is going to use up alot of memory, you might want to go with the tree instead...

quote:

---

Original post by Yanroy

Stoffel: Have you ever played an online game that says ''loading'' every time you do a hyper-jump with you ship? That would be horrible, especially if it took a long time.

---

You could display some "warping" animation, but no loading text while the game loads, to avoid breaking immersion. Since there are no graphics to load, it could load pretty fast, in a second or a few.

-Jussi

"All in all it was just a brick in the wall.
All in all it was just the bricks in the wall."
- Pink Floyd

One thing to consider is that galaxies like ours are fairly flat compared to their diameter. So, why not think of the area as 128x128x1. This is assuming of course that your game takes place in only one galaxy.

There seem to be quite a few interesting and useful ideas out there... thanks. I don''t know what I will use yet, maybe a tree is the best way to go. Just one question: how does the tree save memory? If it works all the way down to the 1x1x1 sector level, wouldn''t it take sizeof(treenode)*8^n bytes just to store the tree, where n is the number of recursions? I don''t feel like checking that math... if its wrong, who cares. It will still be a lot of memory just to store the tree. Not having nodes with nothing in them cuts down on that A LOT, but as the galaxy gets more populated and the players/NPCs/drifting spacecrafts left over from battles spread out, but remain more or less the same density (d=m/v, volume increases, objects (m) increase, density stays the same), the tree would still gobble memory like there is no tommorrow. Perhaps a tree that only recurses (sp?) two or three levels, so it controls an area of 32x32x32 or something like that, and the rest is coord-comparison. I feel like I''m rambling, so I am going to stop with a few last comments.

Magmai Kai Holmlor: I have never encountered an online text based game with a loading screen... but if you say they exist, I will believe it.

microdot: If I go with the coordinate system, a player''s coords would be like this:

unsigned long int x;
unsigned long int y;
unsigned short int z;
 

That makes it much wider than it is tall (65536 times?). That is both more realistic and cuts down on the number of comparisisons. It may be more realistic to define x and y as short ints and z as a byte... that would make the proportion better. The advantage of doing this is that when someone flys over the edge of the universe, I don''t have to add any code to wrap them to the other side

--------------------


You are not a real programmer until you end all your sentences with semicolons; (c) 2000 ROAD Programming

You are unique. Just like everybody else.

Yanroy@usa.com

Visit the ROAD Programming Website for more programming help.

quote:

---

Original post by Yanroy

There seem to be quite a few interesting and useful ideas out there... thanks. I don''t know what I will use yet, maybe a tree is the best way to go. Just one question: how does the tree save memory? If it works all the way down to the 1x1x1 sector level, wouldn''t it take sizeof(treenode)*8^n bytes just to store the tree, where n is the number of recursions? I don''t feel like checking that math... if its wrong, who cares. It will still be a lot of memory just to store the tree. Not having nodes with nothing in them cuts down on that A LOT, but as the galaxy gets more populated and the players/NPCs/drifting spacecrafts left over from battles spread out, but remain more or less the same density (d=m/v, volume increases, objects (m) increase, density stays the same), the tree would still gobble memory like there is no tommorrow. Perhaps a tree that only recurses (sp?) two or three levels, so it controls an area of 32x32x32 or something like that, and the rest is coord-comparison. I feel like I''m rambling, so I am going to stop with a few last comments.

---

Are you now talking about the server software or the client software? The client software doesn''t have to have all parts of the world loaded in memory at once, just the neighbouring areas. At tree should help here. As for the server software, don''t keep unpopulated areas in memory, not even pointers to them. Or how is your game structured? I don''t know. In any case, the point is: keep data you don''t need and won''t be needing in the near future on the hard drive.

-Jussi

(quote space for sale (for free))