Author Topic: Moving the @  (Read 10661 times)

Pueo

  • Rogueliker
  • ***
  • Posts: 263
  • Karma: +0/-0
    • View Profile
    • Email
Moving the @
« on: May 05, 2012, 02:37:06 PM »
Question time again!

Say I have a map.  I have the map stored in an chtype array[30][125] (the size of the map).  If I have my '@' character, then the player wants to move the '@' up, I do this:

// Find the '@' character's coordinates, then:
mvaddch(coory, coorx, chtype array[coory][coorx]); // To overwrite the old '@' with the original tile
// Then print the '@' one space north.
// Coory is the 'y' coordinate of '@', same with coorx, but with 'x'

Is that right?  If it is, then how do I find the '@' symbol?
If it's not, how would I do it? And then, how do I find the '@' symbol?

My guess is to read the screen until it comes across the '@', but I don't know how I would do that.
Or, should I just store a couple variables with the @'s coordinates that I printed it with, then use those?
{O.o}
 |)__)
   ” ”   o RLY?

BrightBit

  • Newcomer
  • Posts: 16
  • Karma: +0/-0
    • View Profile
    • My artwork gallery
Re: Moving the @
« Reply #1 on: May 05, 2012, 03:09:08 PM »
Hi,

maybe I am missing the point but why do you need to >find< the @? You should always know its position.

x/y 01234

0   #####
1   ###@#
2   #####

If the "array" above is your current situation you already should know that the @ is at (3, 1). If the player now presses up you immediately know the new position (3,0) without 'finding' the @.


Greetings
BrightBit
« Last Edit: May 05, 2012, 03:23:05 PM by BrightBit »

XLambda

  • Rogueliker
  • ***
  • Posts: 208
  • Karma: +0/-0
    • MSN Messenger - tau_iota@live.de
    • View Profile
    • The Weird Rogue
Re: Moving the @
« Reply #2 on: May 05, 2012, 03:10:48 PM »
Normally, if you use object-oriented programming, your hero is an instance of a class. Then you have variables hero.x and hero.y. In the case of pure procedural, you most likely represent your hero using something like a struct in c. This struct would then contain the x and y variables.

What you would do then is adjust these for the position after moving, then printing the @ at the new coordinates.
So normally you do something like this (pseudocode):

hero.x += dx;
hero.y += dy;
print(hero.x, hero.y, '@');

dx and dy being the offset of the new position. This works for every object in the game, though you will probably want to add dedicated printing functions/methods.
« Last Edit: May 05, 2012, 03:13:02 PM by XLambda »

kraflab

  • Rogueliker
  • ***
  • Posts: 454
  • Karma: +0/-0
    • View Profile
    • kraflab.com
Re: Moving the @
« Reply #3 on: May 05, 2012, 04:18:17 PM »
Furthermore, you are probably going to want a tile to be represented as a class as well.  That way you can set tile.character=player or monster, etc.  It's much more reasonable if you want to know what is on a tile to look at the tile stored at x,y and see it's properties.  I.e. if you have ten different things on a tile, just looking at what text is there doesn't tell you the whole story.  Of course you *can* have like 15 arrays storing all these things, but just having an array of the tile class or some other such thing seems a lot more sensible to me.  It's also much faster to only iterate over 1 array as opposed to iterating over 15 of the same size.

Pueo

  • Rogueliker
  • ***
  • Posts: 263
  • Karma: +0/-0
    • View Profile
    • Email
Re: Moving the @
« Reply #4 on: May 05, 2012, 07:23:42 PM »
Hi,

maybe I am missing the point but why do you need to >find< the @? You should always know its position.

Greetings
BrightBit
Well, at first I was thinking about if the @ was printed at a random location, but then I realized that the random location would still be logged, so the 'point' was really just me not thinking things through.  But thanks for your input.

In the case of pure procedural, you most likely represent your hero using something like a struct in c. This struct would then contain the x and y variables.

hero.x += dx;
hero.y += dy;
print(hero.x, hero.y, '@');

dx and dy being the offset of the new position. This works for every object in the game, though you will probably want to add dedicated printing functions/methods.

Thanks, I will have dedicated functions (take in a character and move it north/south/east/etc), and I'm writing C, so it will be a struct.

Furthermore, you are probably going to want a tile to be represented as a class as well.  That way you can set tile.character=player or monster, etc.  It's much more reasonable if you want to know what is on a tile to look at the tile stored at x,y and see it's properties.  I.e. if you have ten different things on a tile, just looking at what text is there doesn't tell you the whole story.  Of course you *can* have like 15 arrays storing all these things, but just having an array of the tile class or some other such thing seems a lot more sensible to me.  It's also much faster to only iterate over 1 array as opposed to iterating over 15 of the same size.
At most I will have 1 item per square (for simplicity's sake), so the 15 arrays thing won't be as much of a deal for me.  

Thanks for your input guys, I guess my problem wasn't really a problem after all.
{O.o}
 |)__)
   ” ”   o RLY?

requerent

  • Rogueliker
  • ***
  • Posts: 355
  • Karma: +0/-0
    • View Profile
Re: Moving the @
« Reply #5 on: May 05, 2012, 09:34:52 PM »
You should make plans now to keep your rendering and logic separate. The game doesn't need the '@' symbol or the display functions/screen to know what's going on. Keeping them separate makes it easy to drop in support for different graphics libraries/tiles.

Pueo

  • Rogueliker
  • ***
  • Posts: 263
  • Karma: +0/-0
    • View Profile
    • Email
Re: Moving the @
« Reply #6 on: May 06, 2012, 12:16:51 AM »
You should make plans now to keep your rendering and logic separate. The game doesn't need the '@' symbol or the display functions/screen to know what's going on. Keeping them separate makes it easy to drop in support for different graphics libraries/tiles.
Great advice, thanks.
{O.o}
 |)__)
   ” ”   o RLY?

Ancient

  • Rogueliker
  • ***
  • Posts: 453
  • Karma: +0/-0
    • View Profile
Re: Moving the @
« Reply #7 on: May 06, 2012, 09:24:19 PM »
Furthermore, you are probably going to want a tile to be represented as a class as well.

I disagree.

Quote
Of course you *can* have like 15 arrays storing all these things, but just having an array of the tile class or some other such thing seems a lot more sensible to me.

ZapM has six. PRIME may have one more in future. I rarely go for "sensible" solutions. I prefer those that are easy to maintain and get me good results. For me array of structures also seemed more inviting at first but it makes tampering with map layers much more difficult for no reason. You can't compute a conjunction of map monster array and array representing inverted annihilation cloud to get rid of all creatures in certain area. Shifting clouds can be done with simple celluar automaton which does not need to know the map holds monsters, items and so on if you have separate array for gases. Otherwise it does because you pass the whole structures. Well, you could pass the offset of variable in structure instead but I deem such solutions as undesired in general.

Quote
It's also much faster to only iterate over 1 array as opposed to iterating over 15 of the same size.

This statement holds. But please consider how often do you iterate over your single array and access *all* of its elements sequentially? I do it only a single time: upon level creation when everything is zeroed out. If you scan your array only looking for monsters (for example to resolve grenade explosion) this is actually slower because you read larger chunks of data (a whole structure) of which you only need the pointer to monster. When I distribute monsters on a newly created map only terrain layer matters. Same for using transportation ray gun and having to carry of some creatures. Sure, there are other circumstances where access to several layers is needed but rarely more than two at once. In practice 15 arrays are much faster than single array. Still, the difference is probably negligible enough to not allow it to influence your design.
Michał Bieliński, reviewer for Temple of the Roguelike

kraflab

  • Rogueliker
  • ***
  • Posts: 454
  • Karma: +0/-0
    • View Profile
    • kraflab.com
Re: Moving the @
« Reply #8 on: May 07, 2012, 12:03:53 AM »
I disagree.
This is unfathomable to me.  Perhaps the problem is c vs. c++.  Of course the methods in c++ are what leads me to question why anyone would use c except for the sake of faster execution with computationally heavy projects.  It's much easier to have tile[x,y].draw instead of for instance ground[x,y].draw; creature[x,y].draw; item[x,y].draw; ... etc.  When you add a new layer, you can just edit the tile.draw method instead of adding a new array everywhere that arrays get accessed.  This is also where the accessing a lot of arrays i mentioned comes into play.  However if your game is ascii or otherwise single-layered than I guess it is not a big deal.

For me array of structures also seemed more inviting at first but it makes tampering with map layers much more difficult for no reason. You can't compute a conjunction of map monster array and array representing inverted annihilation cloud to get rid of all creatures in certain area.
If storing things as objects complicates things, you're doing it wrong (Or maybe the code just needs to be completely rewritten.  I can understand if *that* is the barrier).

If you scan your array only looking for monsters (for example to resolve grenade explosion) this is actually slower because you read larger chunks of data (a whole structure) of which you only need the pointer to monster.
Are you nitpicking that a[x,y] is faster than a[x,y].monster?  Come on!

I'm not trying to say that one way of writing code is any better than another, but there are certain good design principles that you pick up over time and I just wanted to bring that up.  When you write code with objects instead of separate elements, which is kind of a higher-order hard-coding, it makes the game much more extendable (not to mention legible).  Of course given that this is the community that shuns/disregards graphics and interfaces, it doesn't surprise me that people also don't like oo programming =P

requerent

  • Rogueliker
  • ***
  • Posts: 355
  • Karma: +0/-0
    • View Profile
Re: Moving the @
« Reply #9 on: May 07, 2012, 03:49:24 PM »
I'm confused by both of what you're saying.

Quote from: Ancient
But please consider how often do you iterate over your single array and access *all* of its elements sequentially? I do it only a single time: upon level creation when everything is zeroed out. If you scan your array only looking for monsters (for example to resolve grenade explosion) this is actually slower because you read larger chunks of data (a whole structure) of which you only need the pointer to monster.

The oop method is to make it so that all objects inherit from a base object class typically starting with two other abstracts: passive and active (not really necessary). All objects in the active list are polled each turn for an action (active.update), whereas passive is the set of objects that can only be acted upon (walls, items, etc, static gas). For collision detection, we might have a map[x.y] where each element is a list of pointers to the objects that occupy that square (in order of graphical display). This has the double benefit of allowing us to cache the screen on update, making it so we only need to redraw tiles that have actually changed (I assume this is happening no matter what method a person is using).

When an explosion takes place, all we care about are the map tiles that the explosion collides with (whether it is a state-progression over several turns or resolved immediately). We only need to check the salient tiles (radius from origin), not entire lists or the entire map.

In this way, I agree that the tile shouldn't be an object, but if we have destructible walls then every tile will at least have a floor/pit. Regardless, I don't see why you need to even think about 'whole' anythings.

Quote
If you scan your array only looking for monsters (for example to resolve grenade explosion) this is actually slower because you read larger chunks of data (a whole structure) of which you only need the pointer to monster.

Checking the type of object is too resource-intensive? You're not reading the whole structure, just checking the pointer for what type of data structure it points to. That's pretty harmless. With a nice inheritence hierarchy you can very intelligently search for types of things.

Quote from: kraflab
This is unfathomable to me.  Perhaps the problem is c vs. c++.  Of course the methods in c++ are what leads me to question why anyone would use c except for the sake of faster execution with computationally heavy projects.  It's much easier to have tile[x,y].draw instead of for instance ground[x,y].draw; creature[x,y].draw; item[x,y].draw; ... etc.  When you add a new layer, you can just edit the tile.draw method instead of adding a new array everywhere that arrays get accessed.  This is also where the accessing a lot of arrays i mentioned comes into play.  However if your game is ascii or otherwise single-layered than I guess it is not a big deal.

The use of a tile object in your description is somewhat confusing to me-- is it strictly a container for the objects occupying the tile?

Each object is mapped to or references an asset (whether it is a character, a tile, or a sprite). We keep our rendering and logic separate, so we have separate update and render methods. A call to render tells the graphics to draw the calling object at its position (pending on how/if we buffer, we need to update all effected tiles- such as those that the object is leaving). If we think of things as a scenegraph, the object is parented to its location-- in this case, a tile object. The tile object orders its children in regards to each child's type (the ancestor class for monster will have precedence over the ancestor class for ground-- we want to preserve awareness so we can accurately draw backgrounds if necessary- similarly, some ancestors, like gas or lights, will have even higher precedence being drawn as filters).

Given this paradigm, we ONLY need to call the render method of a tile whenever the appearance of a child changes (highlighting/fading gas/etc) or when a child is gained/lost (movement/death/etc).

Is this more or less what you're talking about?


Quote from: Ancient
You can't compute a conjunction of map monster array and array representing inverted annihilation cloud to get rid of all creatures in certain area. Shifting clouds can be done with simple celluar automaton which does not need to know the map holds monsters, items and so on if you have separate array for gases. Otherwise it does because you pass the whole structures.

Why would you want to perform a conjunction? Is it significantly more efficient than collision detection? I would assume no, since CD is going to only check/effect tiles that are directly influenced. A conjunction is going to mash together a whole ton of empty cells or cells that don't have anything to do with the annihilation cloud (unless you do some fancy culling).

Why not just have a particle engine that manages each cloud-tile object? You never need to know anything apart from which tiles are occupied by gas and what state each gas-tile is in. It's possibly a simpler implementation of an automaton. In the game-loop, the gas-cloud gets updated with every other active object, its own update method calls all of its cloud-tile updates to see what each one does. It makes colliding very light on resources- no arbitrary searching or nonsense. Only tiles that are involved in state-changes get looked at.
« Last Edit: May 07, 2012, 04:04:19 PM by requerent »

kraflab

  • Rogueliker
  • ***
  • Posts: 454
  • Karma: +0/-0
    • View Profile
    • kraflab.com
Re: Moving the @
« Reply #10 on: May 07, 2012, 06:55:51 PM »
Quote from: kraflab
This is unfathomable to me.  Perhaps the problem is c vs. c++.  Of course the methods in c++ are what leads me to question why anyone would use c except for the sake of faster execution with computationally heavy projects.  It's much easier to have tile[x,y].draw instead of for instance ground[x,y].draw; creature[x,y].draw; item[x,y].draw; ... etc.  When you add a new layer, you can just edit the tile.draw method instead of adding a new array everywhere that arrays get accessed.  This is also where the accessing a lot of arrays i mentioned comes into play.  However if your game is ascii or otherwise single-layered than I guess it is not a big deal.

The use of a tile object in your description is somewhat confusing to me-- is it strictly a container for the objects occupying the tile?

Each object is mapped to or references an asset (whether it is a character, a tile, or a sprite). We keep our rendering and logic separate, so we have separate update and render methods. A call to render tells the graphics to draw the calling object at its position (pending on how/if we buffer, we need to update all effected tiles- such as those that the object is leaving). If we think of things as a scenegraph, the object is parented to its location-- in this case, a tile object. The tile object orders its children in regards to each child's type (the ancestor class for monster will have precedence over the ancestor class for ground-- we want to preserve awareness so we can accurately draw backgrounds if necessary- similarly, some ancestors, like gas or lights, will have even higher precedence being drawn as filters).

Given this paradigm, we ONLY need to call the render method of a tile whenever the appearance of a child changes (highlighting/fading gas/etc) or when a child is gained/lost (movement/death/etc).

Is this more or less what you're talking about?

Yes.  If i was unclear, i meant "tile" as in a container object.  So you might have tile.ground, tile.monster, tile.items, etc for all the things that might be drawn on a tile.  I would also keep all the information, for instance pathfinding data, in that container for simplicity, although I can understand having a container that only has drawing-pertinent information and another that has other data.

Ancient

  • Rogueliker
  • ***
  • Posts: 453
  • Karma: +0/-0
    • View Profile
Re: Moving the @
« Reply #11 on: May 08, 2012, 02:52:16 PM »
I disagree.
This is unfathomable to me.  Perhaps the problem is c vs. c++.

No. Man, demolishing myths is difficult.

Of course the methods in c++ are what leads me to question why anyone would use c except for the sake of faster execution with computationally heavy projects.  It's much easier to have tile[x,y].draw instead of for instance ground[x,y].draw; creature[x,y].draw; item[x,y].draw; ... etc.

Sure thing. PRIME has it but "tile" is replaced by "map". To have such calling convention you do not need to have tiles as objects. To me tiles are merely data which map manipulates. The map itself is an instance of a class. And data ought to be in format best suited to data processing. Do not multiply entities beyond reason.

When you add a new layer, you can just edit the tile.draw method instead of adding a new array everywhere that arrays get accessed.

Umm... why I would need a new array everywhere the arrays get accessed? I do not remember anything like that in my code. I do edit map.drawSq method for all my needs. There any new arrays are handled. Nothing outside map is aware I have series of arrays inside. A new array in map is a new array but only there. For example when I need to know what monsters are in certain radius from a point the list of creatures present on map is scanned. When specific position is queried the check is done by accessing the array (which serves as cache). Outside objects polling the map for whatever have no idea what is going within. The definition of tile (shSquare in PRIME) is not exported.

This is also where the accessing a lot of arrays i mentioned comes into play.  However if your game is ascii or otherwise single-layered than I guess it is not a big deal.

All my games are ASCII but there is more than one layer of display in fact. Interface just queries the map to know what is displayed and the map decides what needs to be returned. Results vary depending on capabilities of player character. BOSS is different but the software is really ancient. Also, BOSS unlike other games does not utilize OOP much. What is most funny BOSS does use the tile stores all the stuff approach.

For me array of structures also seemed more inviting at first but it makes tampering with map layers much more difficult for no reason. You can't compute a conjunction of map monster array and array representing inverted annihilation cloud to get rid of all creatures in certain area.
If storing things as objects complicates things, you're doing it wrong (Or maybe the code just needs to be completely rewritten.  I can understand if *that* is the barrier).

It does not complicate things. It simply brings zero benefits. I could rewrite without much troubles it because map code is nicely isolated but why bother doing it? There is nothing to be gained. I would rather implement some feature. Plus objects cost more memory than plain old data but this is a minor point.

If you scan your array only looking for monsters (for example to resolve grenade explosion) this is actually slower because you read larger chunks of data (a whole structure) of which you only need the pointer to monster.
Are you nitpicking that a[x,y] is faster than a[x,y].monster?  Come on!

Come on, of course not! I took some knowledge of computer architecture for granted which you appear to not have. Whenever the CPU accesses some region of memory the required part and more gets copied to processor internal cache. Operations on cache are much faster than RAM accesses. The trick is cache memory is small. When you copy whole structures you copy a lot of data you won't be using and thus need to access RAM more often. Which is slower.

I'm not trying to say that one way of writing code is any better than another, but there are certain good design principles that you pick up over time and I just wanted to bring that up.  When you write code with objects instead of separate elements, which is kind of a higher-order hard-coding, it makes the game much more extendable (not to mention legible).  Of course given that this is the community that shuns/disregards graphics and interfaces, it doesn't surprise me that people also don't like oo programming =P

Are you assuming I am totally opposed to OOP? Go have a look at PRIME source code. What I dislike is brainless application of OOP. This topic of array of structures versus structure of arrays crops up on rgrd sometimes. I think one of most interesting posts about the latter approach is made by Jeff Lait. That man has even more reasons to pursue it. There are also more arguments why this is faster than what you suggest. Here: link.

Applying OOP does not make things magically more extendable or more legible by definition. Both are function of how good a programmer is with each programming paradigm. If you cannot read procedural code well you may get the result you speak of but I am pretty sure it is not your case.

I do not disregard graphical interfaces either but that is another long story.
Michał Bieliński, reviewer for Temple of the Roguelike

kraflab

  • Rogueliker
  • ***
  • Posts: 454
  • Karma: +0/-0
    • View Profile
    • kraflab.com
Re: Moving the @
« Reply #12 on: May 08, 2012, 05:38:21 PM »
Are you nitpicking that a[x,y] is faster than a[x,y].monster?  Come on!

Come on, of course not! I took some knowledge of computer architecture for granted which you appear to not have. Whenever the CPU accesses some region of memory the required part and more gets copied to processor internal cache. Operations on cache are much faster than RAM accesses. The trick is cache memory is small. When you copy whole structures you copy a lot of data you won't be using and thus need to access RAM more often. Which is slower.
Actually this is exactly what I said.  You are saying that calling a[x,y] (some random info) is faster than calling a[x,y].monster (which has to copy some big container a, and then access monster) as the number of calls increases.  My point was that both actions take pretty much no time.  I mean, it takes 0 ms for my game to do everything except draw the screen, so I really don't think it is measurably slower than whatever way you are doing it.  I'm sure there is some limit where it matters, and on certain computers.

Applying OOP does not make things magically more extendable or more legible by definition. Both are function of how good a programmer is with each programming paradigm. If you cannot read procedural code well you may get the result you speak of but I am pretty sure it is not your case.

I do not disregard graphical interfaces either but that is another long story.

After reading your post, I am pretty sure we actually completely agree on everything, but we were using different language to talk about it and confused each other :P This is probably my fault because I tend to simplify the things I say into possibly confusing shorthand at times ;)

Z

  • Rogueliker
  • ***
  • Posts: 905
  • Karma: +0/-0
    • View Profile
    • Z's Roguelike Stuff
Re: Moving the @
« Reply #13 on: May 08, 2012, 07:20:50 PM »
From the programmer's point of view, it is important that you have some kind of a position identifier, pos. And then you should be able to access the properties with something like tile[pos] or M[pos].tile or pos.tile(). What exactly you write is a matter of taste. You can have two numbers (x,y) as an identifier, but this is often very inconvenient.

My HyperRogue is special here since there is no effective coordinate system. Therefore it makes no sense to have position identifiers be anything else than pointers to structs which contain all the data about the given cell. At least I don't see any other feasible option.

I have looked at my Hydra Slayer's source and I often need to access 3 or 4 properties of the single cell at once. By using a cell struct, I can calculate the pointer to the cell once, and then use it as many times as I need. And calculating the pointer in Hydra Slayer is a bit more complicated than a[x,y] due to the Klein bottle topologies of some levels, so calculating it once is fast and convenient.

Regarding the CPU cache, structs of arrays are optimized for accessing the same property of neighboring cells, and arrays of structs are optimized for accessing different properties of the same cell. It is hard to tell which is more important. Anyway, I don't think it is that important since the whole map should fit in most cases, the differences are not really that big, and it will probably run fast anyway.

Quote
You can't compute a conjunction of map monster array and array representing inverted annihilation cloud to get rid of all creatures in certain area.

I don't understand what's the problem here...

Ancient

  • Rogueliker
  • ***
  • Posts: 453
  • Karma: +0/-0
    • View Profile
Re: Moving the @
« Reply #14 on: May 10, 2012, 05:34:03 PM »
@kraflab: I am not opposed to the thing that both approaches take little time. What I don't agree with is the single array of structures is faster in general. Otherwise we seem to be pretty much in sync as you pointed out.

@Z: Yes, Hyperbolic Rogue is very special in this regard. Jacob's Matrix sources might be enlightening but I have no idea whether it has a coordinate system.
Michał Bieliński, reviewer for Temple of the Roguelike