Server Help

[VampZ]

you need to add a:

if (!reg) continue;

after

else if (!strncasecmp(buf, "isbase", 6))

or else it might try to dereference a null pointer if the first line after the header is "isbase"... haven't tried it myself, but i have plenty of experience dereferencing null pointers.

also: why isn't the region file just type in the regions using ascii numbers... 10 bit integers? be real grem

also, when you add coords to the .rgn file a hash table would be better than the dynamically expanding array it looks like you're going to use.

[VampZ]

fyi, that's in:
mapdata.c

in function:

HashTable * LoadRegions(char *fname)

[Grelminar]

First, the region stuff is really old and due to be replaced with something better.

Second, I was trying to come up with a format that was unambiguous and easy to input and output by code, since the region files were supposed to be generated by the map editor. In retrospect, I agree it's dumb.

Third, a hash table would be worse. What would the key be? The idea is to be able to iterate through a bunch of rectangles quickly. What might potentially be better is a bunch of sparse array representing bitmaps. But that would use a lot more memory, especially for large regions.

[Dr Brain]

Personally, I would like to see a master region file that references multiple bitmap files. These files would be color coded, and could be simply colored versions of a FACTS .bmp output.

The master file is so that regions would be able to overlap, something you couldn't do with a single bitmap file.
_________________
Hyperspace Owner

Smong> so long as 99% deaths feel lame it will always be hyperspace to me

[Grelminar]

That's not bad, though I'd also want some program to compress all that information into one smaller file, so you don't have to be uploading multiple megs of bmp files with every new map.

Even better would be if the information could be encoded in the .lvl file itself. Encoding it is actually the easy part. But my ideal vision would be for the lvl editor to support editing and embedding region information itself. For that to happen, I'd need source code for a decent map editor. And I don't think there is such a thing floating around.

[Mr Ekted]

I think the best generic solution is some form of BSP or derivation thereof.

For a small # of regions (maybe < 20), you are better off just walking an array and testing. For a huge # of regions (say 50,000), you are better off having a 1024x1024 array with region indices (yes a ton of memory).
_________________
4,691 irradiated haggis!

[Bak]

Hash Table would be worse?

You could use the two coordinates as the key, 10 bits each -> 20 bits + you can't use 0 for any of the bytes 'cause the key must be null terminated -> 23 bits... so 3 bytes + null terminator = 4 bytes. That saves space over the current setup where you have two 4 byte integers and a 4 byte pointer to the next one... anyways I think i'll try to make something, and if you want, you could use it.

The hash table would be cool if you could pass it a hashing function so that it wasn't limited to char*'s for the key, but that's not a big deal.

The thing is right now I'm loading a bunch of rectangles that are 1x1 and there's like 200 of them, so it has to go through approx 100 every time it does a lookup.

For a medium number of regions, an alternative to a 1024x1024 array may be just two 1024 arrays of linked lists, then when you want to add a coordinate at 405,407 it would add your region to 405 in one array and to 407 in another... and when you check is a player in that region you can lookup the x and lookup the y and see if they both have that region at the cooresponding coordinate. Loading rectangles you'd have to go through every point and add it, but you'd have to do that for the 1024x1024 array too. You can also use arrays of hash tables instead of linked lists if you want constant time lookup.

-VampZ

[Mr Ekted]

Hash table by tile is really bad. Requires an array of at least 2 million elements (double the # of tiles).

Your other idea, a 2 dimensional sparse matrix, is good. Only store used coords in array (and group into contiguous values), sort by value, and use binary search in the y direction, then in the x direction. At most, there would be 20 compares to find a region, and only in the most complex case. As you stated, you could also do a full 1024 coords in the y direction, and sparse in the x direction. A bit more memory, but faster. The trick here is setting up the sparse matrix efficiently. I can picture exactly how to do it, but I don't feel like going into detail unless someone really wants to know.