Data type for storing lvl tiles?

[Marioman]

I'm curious what data type you guys think would be best for indexing tiles. Could the devs for existing projects (like DCME, Discretion, jab jab jab's java client) maybe share a bit on how they do it?

 

Some options i found on wikipedia

 

Why i'm asking is because i'm trying to make a bot that can navigate a map so it would be good if i could get all tiles within a certain distance away. Also performance is critical.

 

I started out with a quadtree since that's the only thing i'm familiar with and it's easy to implement.

http://i.imgur.com/VCHyB.png

[Dr Brain]

I think a quadtree is the most obvious for accessing local tiles quickly.

 

Though to be perfectly honest, a fully populated 1024x1024 byte array would only consume 1MB. Not really a bad way to go in this age of 4GB memory being standard on new computers. I don't think any other data structure will be faster than this.

[Cheese]

the asss server platform is open source, and what you are looking for can be found in mapdata.c

 

additionally, i wrote a server side ai bot platform a few years ago, which i plan to make open source in perhaps a month after i finish adding in repels, wormholes, and bricks, which i have to reverse engineer priit's math for.

http://forums.minegoboom.com/viewtopic.php?t=8858

 

it already uses single tier (not stacked) pathfinding

i can give you a live demonstration if you are interested.

[Marioman]

@Dr Brain yeah i didn't think of doing that. If i did go that route i could just encode whether the tile is traversable in a single bit and have a 1024x1024 single bit array... would only be 128kB! However i still think i would need nice way to group the tiles on the map so i might be able to create a connection graph for macro-path-finding.

 

@Cheese a live demonstration would be super cool. Also i'm curious, and i had asked this a while ago on your other thread cheese: in what way are you making your bot fly the path? (or are you sending position packets in a way to make it look like the bot follows the path)

Edited May 5, 2012 by Marioman

[Marioman]

oh yeah and it looks like ASSS uses sparse arrays, however i'm not sure since i don't understand the #include "sparse.inc" in mapdata.c. There's no sparse.inc file in the ASSS source, and in the makefile it has this

 

# generated file for mapdata
$(call tobuild, sparse.inc): $(builddir) $(SCRIPTS)/gensparse.py $(SCRIPTS)/sparse_params.py
$(PYTHON) $(SCRIPTS)/gensparse.py $@ $(SCRIPTS)/sparse_params.py

 

but i don't know where any of the sparse python files are located.

[Cheese]

if a bot sends position packets just like a real player, noone else will ever be able to tell the difference

 

also:

:cheese!: i want to see ai bots

[Dr Brain]

A bit array is more compact than a byte array, but it may not be faster since you'll have to do bit operations to get the tile you want. Of course there's all sorts of cache considerations that reverse this conclusion, but I figured the simpler data structure (programatically) was still the best one.

 

However i still think i would need nice way to group the tiles on the map so i might be able to create a connection graph for macro-path-finding.

 

map[j] is connected to map[i+1][j], map[i-1][j], map[j+1], map[j-1], with appropriate edge of map detection. What more do you need than this?

[Marioman]

Yeah it hadn't occurred to me that there isn't a type the holds a single bit haha so you're right a byte array is probably more practical.

 

map[j] is connected to map[i+1][j], map[i-1][j], map[j+1], map[j-1], with appropriate edge of map detection. What more do you need than this?

 

For path finding over large regions i wanted to decompose the map into a set of regions that were connected and had adjacency information so there would first be a global path finder then a local path found through the global path's regions. Giving that idea a bit of thought though, i think it's a different problem irrelevant to how i'm storing the tiles.

[Marioman]

Actually I think the quadtree might be able to be used as a suitable navmesh.

 

Do an A* search, if entering region with the number of tiles greater than or equal to (region width) - (width of ship) in the search i'd have to make sure there are paths north/west/east/south of this tile (inefficient). Of course i can make the cost value of each region in the search weighted based on how gray it is (what % of it is tiles).

 

Currently in the quadtree i split up a region and create child regions when one exceeds a max amount of tiles (16 in picture).

Instead, to ensure i don't have a lot of medium sized regions with tiles numbering region width, I can decompose until their grayness is at a certain percentage (e.g. 25x25 region with one vertical blocking segment of 25 pixels has grayness 1/25 while a 10x10 segment with one vertical block of 10 pixels has grayness 1/10).