algorithms and datastructures

/prog/ i have a problem

for the past couple of years i have been fooling myself into
thinking i am a programmer. i would pick up a new language every
few months, write a few toy programs in it and convince myself
that, since i knew how to write fibs, i knew how to make
something.

turns out all i'm capable of doing is shoveling data back and
forth between the user and some API. i am not capable of
designing complicated data-structures or algorithms to
query/modify them.

i have come to that conclusion when i was faced with some
problems regarding the design of my /prog/ roguelike server. i
wanted something that scaled better than my current solution: a
simple list of (x,y,entity). i quickly found myself humbled in
the land of spatial databases.

so /prog/, how would i go about saving loads of entities? i
already have a tile map[x][y] but i might want to
have lot's of entities of a single tile (dead body, armour,
weapon, gold) so i can't just add an entity pointer to tile.
also i want to keep my tile small (one or two bytes) so i can
have bigger maps. i'll need to make something like a quadtree
but what if i want to have a shittun of items in the same place
and my nodes overflow?

opiates

you could try adding pointer to a linked list of entities

For a second I thought this was going to be interesting.
It's all about how you're going to access things, but you can do >>4, or a variation with time/space tradeoff by binning things into larger areas.
You certainly don't need a quadtree to store entities for your roguelike. Though similar structures could be useful to generate and store map data if maps are sparsely featured.
I hope you have this all abstracted, so you can start with a simple implementation and swap it out later.

>>5
yeah, everything is abstracted, don't worry :-)

my main problem with the idea of using a single list (or adding a linked list to map[][] like >>4 suggested) is the complexity of finding all entities in a certain region: using a simple single list this is O(N) w.r.t. the total amount of entities, >>4-san's solution is O(N) w.r.t. the size of the area being queried, same with using bins.

i'd prefer to sacrifice some space to get some more performance.

>>6
What's your load factor per <x,y> pair, ``faggot''?

.. 1
. API.

you lost me here, uppercase lover1

>>7
that's a bit hard to guesstimate at this point, i'd say there'll probably be entities in 10-20% of all <x,y> pairs, but as soon as an entity dies all of it's items drop into the square so then there'll be quickly up to 10 items in a single square.

>>6
How large areas do you expect to be querying, then, and how often?
If the expected number of entities also grows linearly with area, your savings are going to be very modest.

^{:GJS1M 67dcbdbce4a0b67c4b48e86a6ae29205a95e4b83024a9d947213d1231800e8d9
:45 79c62da5899e162121f2a4b0dcf089f8
:1298934707 1299007863}
>>7
<-- check 'em dubz

“Bottlenecks occur in surprising places, so don't try to second guess and put in a speed hack until you have proven that's where the bottleneck is.”

- Rob Pike

>>12
choosing a suitable algorithm/datastructure isn't a premature optimisation... it's a part of the design process.

>>13
It can be. It's best to choose the most general data structures (which aren't TOO slow) and use that and then specialize for performance later on when you need it.

>>13
I think the keywords are second guess and speed hack. Choosing an efficient algorithm and data structure is not necessarily the same as premature optimisation.