Good way to store map

quozl

Hi guys,
I need to store a map in memory. It consists of square objects which contain all their own ****e. I was going to use a linked list to store them, but this will not be very effecient when i'm trying to find a particular square or draw the map. I could sort the map, but it still seems worse than just useing an array where i can find the correct square by x,y offsets.
I could sort the list, then to find square x,y, i'd be useing something along the line of
start_of_list+sizeofsquare*x+sizeofsquare*y*widthofmap;
this would give me a pointer to the correct square. This seem like a good idea? Another idea was to use a linked list, then to simply populate an array with pointers to the correct square in the list, kindof like a lookup table.
The reason i'm not simply useing an array which would be effecient and easy, is, I want different size maps. And cant resize arrays on the fly. It would be a bit daft to have a default size array and only use say the corner 32*32 squares. Would linked lists of pointers give a good array approximation.
Any suggestions on what you think would be an effecient and easy way to do this. Thanks
GReg

Void

Just guessing here, ignore me if I'm totally off. If this is for storing the world in your MUD, then I don't think you should try to store the world as a grid. Maybe you are thinking of something else but here's an idea anyway.

All elements (rooms, objects, mobs) of a mud have a location. You can expoit this fact by writing a base class called whatever, which has an ID, a name, a pointer to a whatever outside it, and a pointer to a whatever inside it (a linked list of whatevers inside to be precise). Right, so "whatever" is the base class. Then you can proceed to inherit room classes (add pointers for exits, and a flag for weather maybe), objects classes (add stuff like mass, objecttype - weapon, armour etc), and stuff for mobiles (players/AIs, lots of complicated stuff).

All of these "whatevers" get stored in a table, with their ID as their identifier surprisingly enough. Now, you have a game world in which anything at all can be found by it's ID, which is expandable (dependent on hash size), and is ummm, deadly I suppose. Oh yeah, you can put rooms into objects and other crazy stuff like that (mmm bag of holding).

If I made no sense whatsoever there have a boggers at this link.
http://www-cs-students.stanford.edu/~amitp/Articles/EfficientObjects.html

quozl

I'm comeing from a mud programming background. Spent about 4 years codeing them. But this is for a graphical tile based game, so linked lists strike me as ineffecient during the drawing process, as square 1,1 might be the 37th entry in the list. Sorting it would improve this, but I see problems, as in previous post.
A hash table seemed possible, or if i sort them, the algorith in my first post should give me the correct object without any looping (by just doing some pointer arithmetic). Was just wondering if anyone can think of a much more effecient way todo this, seeing as I dont wanna reinvent the wheel.
I'll quite likely ending up doing something along the lines of what you suggested, but wondering if there is anything blindingly obvious I've missed. Thanks for the link, sadly not too useful. Just some pretty simple stuff about object inheritance. How did you store tile maps, or large grids in programs you've written yourself?
quozl
I'll probably just go with the pointer arithmetic on a linked list, its seems a pretty effecient way to do things.

[This message has been edited by quozl (edited 27-04-2001).]

[CrimsonGhost]

A binary Tree, similar in implementation to a linked listed, but may be quicker when searching for a particular square. let me elaborate
0 = square in grid
- or | the two pointers to other squares. Now some square will have two pointers to them (pointers null if on south/east edges in the example grid below), which isn't exactly binary tree, but you should get the jist of what I'm getting at.

0-0-0-0-0-0-0-
| | | | | | |
0-0-0-0-0-0-0-
| | | | | | |
0-0-0-0-0-0-0-
| | | | | | |

Binary Tree searching is definitely faster than linked lists, but not too sure how the two pointers to some square will work when implemented. May be worth a quick think about. 5 mins max.

And code wise something like
class/struct square{
square *south;
square *east;
other misc data fields and functions
}

[CrimsonGhost]

The pipes in the above grid should all be in the same columns as the zeros, it got reformatted when I posted so now looks a bit off.

quozl

Thanks, I was thinking of something along those lines. Mr Chuffy, suggested I use 4 pointers instead. So given any square I can traverse to another in any direction. 2 more pointers than your way, but could be handy as I'll be getting square objects from objects in the room, and be nice to move from those squares instead of starting at the top of my tree.
I think I'll be putting pointers back up all my linked lists in. It'll be handy for finding say what container a given object is in, or what square a given player is in.
quozl

Trojan

<font face="Verdana, Arial" size="2">Originally posted by [CrimsonGhost]:
The pipes in the above grid should all be in the same columns as the zeros, it got reformatted when I posted so now looks a bit off.</font>

Use [ code ] ubb tag to format (same as <pre> ).

Al.