Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #4679 > unrolled thread

data structure curiosity

Back to article view | Back to comp.programming

Contents

  data structure curiosity b <mike7411@gmail.com> - 2014-08-02 22:50 -0700
    Re: data structure curiosity Richard Heathfield <invalid@see.sig.invalid> - 2014-08-03 08:16 +0100
    Re: data structure curiosity Öö Tiib <ootiib@hot.ee> - 2014-08-04 09:56 -0700
    Re: data structure curiosity "BartC" <bc@freeuk.com> - 2014-08-05 00:46 +0100

#4679 — data structure curiosity

What would be the most appropriate data structure to represent the
ground in a game such as this?

https://play.google.com/store/apps/details?id=cz.gdmt.AnnelidsDemo

I guess you could just use a really big 2d array, but I would hope there is something smarter.

[toc] | [next] | [standalone]

#4680

b wrote:

> What would be the most appropriate data structure to represent the
> ground in a game such as this?
> 
> https://play.google.com/store/apps/details?id=cz.gdmt.AnnelidsDemo
> 
> I guess you could just use a really big 2d array, but I would hope there
> is something smarter.

I only looked at the static images, not any kind of video, but it seems to 
me that there are two components to the background - places you can go 
(tunnels, caverns, etc) and places you can't go (true background).

The true background looks to me as if it's simply a tiled image. You don't 
need a 2D data structure for that (or at least, you need an image, but 
that's all) - you can just replicate the image in a couple of loops:

for(y = 0; y < window_height; y += image_height)
{
  for(x = 0; x < window_height; x += image_height)
  {
    display_image(x, y, imagebuf);
  }
}

except that you'll want to adjust that for the fact that you won't always 
want to start from 0 (presumably the image scrolls as you move around).

For the places you *can* go, that's probably done with a bitmask (to record 
and then determine the limits of the navigable zone).

So you slap the tiled image all over your backbuffer, then overlay the black 
areas (or whatever colour) using the bitmask, then lay your active game 
components (player avatars, missiles, bombs, flowers, energy pills, whatever 
is relevant to your game) over the top, and then flip your buffers.

The interesting bit is how you represent your bitmask. You might usefully 
investigate quadtrees for this aspect. Sure, a quadtree is a 2D data 
structure, but it isn't just a naive bit-by-bit mapping of what you want to 
portray (which is what I think you are rightly trying to avoid).

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#4684

On Sunday, 3 August 2014 08:50:52 UTC+3, b  wrote:
> What would be the most appropriate data structure to represent the
> ground in a game such as this?
> 
> https://play.google.com/store/apps/details?id=cz.gdmt.AnnelidsDemo
> 
> I guess you could just use a really big 2d array, but I would hope 
> there is something smarter.

It seems that there is a background layer that is just painted using 
some background pattern. It just does "see thru" where there are 
nothing on top of it.

Next there is terrain layer that is a (partially erased) picture that
can be altered by activities that erase or add or color it. It
can be kept in memory as big array or array of smaller fragments of
whole picture, up to developer, but it is unlikely compressed in any 
way (if that was what you meant by "smarter").

On top there are the active objects/items that interact with each 
other and the terrain by certain rules of "physics". Snakes are
controlled by players. It is likely some list of such objects that
the program runs through each tick and makes them to do their thing.

[toc] | [prev] | [next] | [standalone]

#4685

"b" <mike7411@gmail.com> wrote in message 
news:d833e796-13fa-40e8-91ea-143c547f7603@googlegroups.com...
> What would be the most appropriate data structure to represent the
> ground in a game such as this?
>
> https://play.google.com/store/apps/details?id=cz.gdmt.AnnelidsDemo
>
> I guess you could just use a really big 2d array, but I would hope there 
> is something smarter.

How big is the 'world' the game is played in? From what I could see of the 
video, it's not too extensive, and not particularly hi-res either. So a 
two-level bit image would do for the main ground layer (the one that's 
destroyed as the game proceeds).

(And which is displayed as a textured and shadowed transparent layer over 
the darker textured background.)

However, using a 256-level image would be simpler and faster to manipulate, 
and lets you directly code it as an array, as not too many languages give 
you bit-arrays to work with directly. It needs quite a bit more memory 
though.

-- 
Bartc 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web