# mike3

Member

59

## Posts posted by mike3

1. ### Cell based game and collisions in discrete space

Simple.
Make one pass to mark objects that want to move as no longer being on the space where they are (calling them “hovering”).
This leaves the space open and others can move into it.

The only problem is that a piece that is hovering may not be able to go where it wants to go, yet can’t land back on its square because it has been stolen.
This is easy to solve, though it involves a small amount of recursion.

When a piece wants to move to a square, if the square is empty (and all other rules obeyed), FinalizeMove(ThatPiece) (remove hovering flag, piece is finalized on the new square, is done processing for that frame, cannot be looked up by the following routines).
If the square, however, has a piece hovering over it, recursively evaluate the piece that is hovering. You terminate the recursion when a piece can move to a square or when you reach any of the pieces that are currently being checked in this recursive call.
This means the pieces rely on each other, and all moves they are trying to make are valid. In this case FinalizeMove() on each piece in the recursive call.
In other words, if any fail, don’t move any of the pieces.
If they all pass, move them all.

L. Spiro

Thanks -- a nice "KISS" method for doing this. I had tried something similar, I believe, but did not use the flag grid, which seems better.

2. ### Cell based game and collisions in discrete space

Hi.

I am wondering about this. I was not satisfied with my previous system for doing this, which seemed kind of ugly or limited, and I was wondering what would be the most efficient and elegant solution.

What I have is a cell-based, turn-based game with a discrete game world, that is, it's a raster of tiles, not a space with (approximately) continuous (floating point) coordinates, with each object in one time. And I was wondering how you deal with collisions. In particular, each object can move but it can, obviously, only move from tile to tile, never be in between two tiles.

This means that when we get collisions, we have a number of cases to consider, and I'd preferably like something better than a casewise approach. Moving one cell at a time, we could have, e.g. that two objects move at each other, their coordinates would change by 1 cell each in opposing directions, causing them to swap places if they were right next to each other. They'd go through each other, so that should be a collision. Another way a collision can occur is that two objects try to rush each other for the same cell. A situation that might look like it would be a collision, but isn't, is two objects moving in the same direction, in the same line, one just behind the other. If you look at only the one in behind, one could think it will collide with the one ahead unless you also look to see which way that is moving, which adds more complicated, tricky programming to make it work on a computer. Things are further complicated by that some objects may move different velocities, crossing multiple squares in a turn (like a shot arrow).

Almost all the collision-handling stuff I've seen deals with continuous space and (approximate) continuous time, e.g. checking overlap, etc. and so does not seem obvious how to apply to a discrete space and maybe also discrete time.

One way I thought to handle it would be to just use a continuous simulation space which is "rounded" to discrete, but then we get a computationally-intensive simulation, as it seems that given the discrete character of the world space, we should be able to simplify/optimize things considerably.

What do you do?

3. ### Programming "Widgets": how do you efficiently draw/redraw windows and widgets?

I don't understand what you're talking about with the overlap. Do you mean draggable windows that float over other windows?

Overlap means yes, windows/widgets overlapping on top of each other. Not necessarily draggable -- just on top of each other, e.g. a menu and then you open up a sub-menu which floats above.

4. ### Programming "Widgets": how do you efficiently draw/redraw windows and widgets?

Hi.

I am wondering about this. I am curious as to how you efficiently program a "widget" GUI system, that is, a part of a program that draws interface windows with buttons and scrollbars and that type of stuff (widgets) on them.

I have done this a couple times before but I was not really satisfied with my previous attempts and am now curious about how you really make it efficient and clean. In particular, what I have is this: I represent the windows and widgets by a tree structure, which is "natural" because it has a natural hierarchical structure, in which the root node represents the whole screen, and then below that we have nodes for the windows, then each window node has nodes for the widgets, then each widget node has nodes for the components of the widget (It could go further, in theory, but this is as far as I go). The order in which the widgets/windows overlap (from front to back) is determined by the ordering of them as siblings on the tree -- the nodes keep pointers to the next sibling in a linked list.

The trouble is that I am trying to figure out how to make the render/drawing as quick and efficient as possible -- in particular, we may know that only certain widgets or components need to be redrawn, so we shouldn't need to explore every node of the tree, but we also have to deal with resolving overlap: we shouldn't redraw something with a higher position on the order if it doesn't actually overlap anything, but we also may not want to keep exploring the whole structure to check for overlaps every time we do a redraw. How can we efficiently do this whole process, including the overlap resolution, the latter ideally without having to check every sibling?

This has to have an already-existing solution since window-based GUIs are so ubiquitous. I am just not sure where to find a good description of it. What would that be?

5. ### Event Handling within an ECS

@Servant of the Lord: Thanks a lot. I think I grasp now how this works. It certainly seems more flexible than trying to shoehorn everything into the "update" routine, probably is more amenable to optimization as well. You don't have to worry so much about trying to fit the system effect to a strict sequencing regiment, either.

6. ### Messages and dynamic memory

Why would we serialize messages? This is about internal communication within the program.

Because it provides one solution to your problem. You can allocate a single block of memory and messages and write themselves into the buffer, etc...

First, I'd make sure you really need a messaging system anyway. Ideally you could replace them with method calls, and that would make the dependencies more clear.

If you really do need some sort of message-like design though (for instance, to be able to queue up messages and process them later), then ask yourself if dynamic allocation will really be a problem (I assume you're worried about performance of dynamic allocation).

Yes, I suppose that you could just use method calls, e.g. inherit from some kind of interface class which is kept suitably loose that implementation details don't leak, but then you can't defer processing until later, which was the purpose of the messaging system.

7. ### Messages and dynamic memory

Well you can send different size messages if theyre prefixed with a size or type.

Like serialize size followed by data (probably the raw memory) in a queue of bytes, and on the other end read the object into contiguous memory (since std::queue is not contiguous) and interpret the address as a Base*.

But unless you actually need something like that for performance reasons, I wouldnt do it because it seems a bit prone to bugs. Maybe if you do proper serialization instead of raw memcpy (or use POD types + switch instead of inheritance) its safer... (does c++ even allow raw memory copy of objects with virtuals?)

Why would we serialize messages? This is about internal communication within the program.

8. ### Messages and dynamic memory

Hi.

I am wondering about this. Is there a good way to do event messages between two large-scale loose-coupled parts of a game program without having to dynamically allocate and deallocate the messages? Messages may need to be queued, and there can be different types of messages, which suggests an inheritance hierarchy and that's where the dynamic memory stuff comes from, at least when using C++ as I'd be in this case. Thanks.

9. ### Event Handling within an ECS

"System" is a description of the architectural pattern used abstractly for reasoning about the code's flow (not the code's purpose). Because all these are named 'system', people automatically go, "I can make them all derived from the same class!" often without a good reason. Occasionally there is a good reason, just as occasionally there is a good reason to put a bunch of unrelated functions in a vector - but by default, the functions shouldn't go in a vector and the systems shouldn't be forced into the same interface. Merely being able to loop over them to call Update(), is not a valid enough reason, and has the detriment that it forces the programmer to artificially cram the diverse, unrelated, systems into a common, uniform, crippled, interface.

It's a crippled interface, because you have to either trim the interface of some systems if you cater to the lowest common denominator, or bloat the interface of the other systems if you cater to the greatest common denominator; i.e. you have to remove functions you should have (as Hodgman points out) crippling it, or add functions you shouldn't have (empty virtual functions) bloating it, to make all systems artificially identical in their interface.

If I'm using the Flyweight pattern for images, and the Flyweight pattern for text, it doesn't automatically mean they should share a common interface and be crammed in a vector.

Systems shouldn't inherit from a base class just because they happen to share the same design pattern. Likewise, different component types shouldn't inherit from an abstract interface just because they happen to be components. Functions shouldn't be crammed into a vector just because they are functions that take the same arguments.

In some code bases, it may make sense, but other people shouldn't do it unless in it makes sense in their framework. In my opinion, as a default one should assume it doesn't make sense unless they have compelling evidence otherwise.

To clarify: I like ECS systems and I'm not against inheritance (and I'm not against polymorphism and the use of inheritance for consistent interfaces when the code needs it). I'm against the use of inheritance in this circumstance, if the only purpose is for putting a dozen or so unrelated classes in a vector for convenience. For codebases with better reasons that that, I have no qualms with.

Or to put it a different way: Just because some classes have an identical interface, doesn't mean they are the same or should be treated the same - and recognizing coincidental interface similarities from similarities genuinely emerging because of similar purposes helps here. This is also where duck-typing, like in C++'s templates, can (sometimes) comes in handy, because you can temporarily treat the interfaces as if they were same when you need to, without actually forcing the interfaces to be the same.

</unnecessarily large dump of conjectured thoughts nobody asked for >

This is a shocker. I am curious: could you run through a few very simple explicit examples of like what kinds of methods would be on a couple of types of system objects built this way in a game? As I'm very used to thinking of the "update" thing. Also, what calls these methods? (With update its obvious: it's just called in the main game loop, but with this, some more diverse code must be doing the calling because the methods are more specific in scope.)

10. ### Question about entity-component-system implementation for doors

Hi.

I was building a game program that uses an "Entity-Component-System" type architecture and was wondering how you would go about implementing doors. In the program as it stands, there are the following requirements:

1. Components should be generic enough that you can form new entity types without a type of component for every type of entity (as that essentially defeats the purpose of the ECS architecture, which is to allow you to make all kinds of things with composition),

2. Components should contain only data, no code.

3. Systems contain all the code for the logic.

4. There is a messaging pipeline where the systems can send messages to each other.

Given this, I am wondering how you would go about implementing doors? It seems that doors require a state and changing that state changes the graphic displayed for the door. Right now, I have a GraphicComponent which stores a key to a graphical asset, and a PositionComponent to store the entity's position. There's also a PhysicsComponent which stores the physical properties of the entity. But if I add a StateComponent to store the door's state, then, when you change states, that has to update the GraphicComponent somehow, and also the PhysicsComponent to make the door passable -- this is a tile-based game, not one taking place in a continuous space. However, because of requirement 1, genericity, we cannot have anything too specific to the door in the StateComponent, but we must specify how to update the other components. But how do we do that without violating requirement 2 -- absence of code in the components? I have a "Finite State Machine" (FSM) object in my program, which would seem to be what I'd want to use, however it's meant to be general (I use it in the user interface to handle various user interface states, such as main menu, playing the game, etc.) so when you make one you specify code, not just data. It would seem it would violate requirement 2 to stick that in the StateComponent.

What is a good way to do this? Should I just use the FSM and see if I can get away with it?

And it gets worse: what happens if you want to have the door be jammed by something else sitting on the door's tile when it's open? Then there needs to be something to sense the object is present. How can you do this without a dedicated system for doors which would violate condition 1?

11. ### Why are static variables bad?

The constructor for Foo now gets gibberish in the whatever field and crashes or behaves in some unpredictable ("undefined") way. It's not that the old code (here, meaning the code that makes the FooContext and the Foo) attempts to use "whatever", it's that the old code doesn't use "whatever", and because it was not updated to take "whatever" into account (meaning, it doesn't even set it to null, it doesn't do anything with it, period), causes Foo's constructor to gag.

So do you add the check for "whatever" not being set in to the old code, in which case it would probably be easier simply to just properly initialize whatever, or do you add the check in Foo, and regardless of the check placement, do you need to add a constructor to FooContext that ensures a stable "uninitialized" or "null" value that can be checked for? Because if you have to add the check and/or set-to-null in the old Foo-using code, then if you forget to add it there, you have a crash or other failure. To me, it seems the only way to make it robust against such omission is to put a constructor in FooContext that pre-initializes whatever to null.

Why would it crash on "whatever" if none of the old code uses it? You literally could have an object with two members, one being a pointer set to gibberish and one being a pointer set to a valid object and as long as you never tried to -use- the gibberish pointer it wouldn't actually do anything undefined.

The way I interpreted the example, the crash occurs when Foo's constructor is invoked with the FooContext having an uninitialized whatever member, and the crash occurs when Foo's constructor is invoked and chokes.

12. ### Why are static variables bad?

Do you mean a check on "whatever"? Since "whatever" was supposed to be the problem variable, as it was supposed to represent a "new feature" that had been added, and all preexisting code (i.e. before the feature addition) only knew of bla. The code already initializes bla.

I suppose I wasn't understanding the example very well. If "whatever" is a member added to the struct later then what would it being set to null matter for old code? Unless the "old code" tried to utilize it then it would essentially be the same as the transparent addition of adding a new variable to a class your code was using, but not utilizing that particular variable.

I'm assuming the point you're getting at is, someone adds the new "whatever" variable to an object, and your code attempts to use the "whatever" object, but your coworker managing the usage of the struct that passes it to you hasn't implemented setting that whatever to something yet. In that case of course you would have to check validity of the object before you use it. If I'm getting this wrong please do re-explain it to me.

The example appears to be: We have a class "Foo" which takes a "FooContext" to specify how to set it up. Initially, this "FooContext" contains only one parameter, "bla". Bits of code are created that have to make Foos from a FooContext, and naturally, they only set bla. But then down the road as our project progresses, someone decides now to add a new feature to Foo, which now requires a new parameter, "whatever", in the FooContext. And in how I imagine this scenario, which may or may not be how kunos imagined it, I imagine "whatever" to be a strictly "extensional" feature, i.e. it does not alter the original behavior of Foo, but extends it to add capability, that is, that the old way of using Foo should still work and not break. (The reason for this requirement is because without it, we might be forced to change the code anyway, but I'm trying to isolate the addition of the data field itself as the problem) But the programmer adding the new "whatever" parameter forgets a place where FooContexts are used and so doesn't add the proper initialization to the extensional feature whatever. The constructor for Foo now gets gibberish in the whatever field and crashes or behaves in some unpredictable ("undefined") way. It's not that the old code (here, meaning the code that makes the FooContext and the Foo) attempts to use "whatever", it's that the old code doesn't use "whatever", and because it was not updated to take "whatever" into account (meaning, it doesn't even set it to null, it doesn't do anything with it, period), causes Foo's constructor to gag.

So do you add the check for "whatever" not being set in to the old code, in which case it would probably be easier simply to just properly initialize whatever, or do you add the check in Foo, and regardless of the check placement, do you need to add a constructor to FooContext that ensures a stable "uninitialized" or "null" value that can be checked for? Because if you have to add the check and/or set-to-null in the old Foo-using code, then if you forget to add it there, you have a crash or other failure. To me, it seems the only way to make it robust against such omission is to put a constructor in FooContext that pre-initializes whatever to null.

13. ### Why are static variables bad?

So what would be the correct approach in the example case, with the struct where a new member may be added? Where would the error be "reported" to, and in what way? More importantly, how would we know "whatever" was uninitialized, when its value as uninitialized may be undefined?

E.g.

FooContext fooContext;
fooContext.bla = <smth>; // old code that didn't know about the new "whatever" feature

// member whatever could have an undefined value, so how does this check that and "report" it, fail gracefully, etc.?
Foo *foo(new Foo(fooContext));

As like he says, it seems you need a constructor of some kind in fooContext to prevent this. Even if not one to force the programmer to pass a parameter, then at least a default one to initialize the variables so their values are all defined (perhaps so as to indicate special uninitialized states that Foo can then check for).

The ideal thing to do would be to treat the context as a volatile object and check for null on .bla before attempting to use it.

14. ### Why are static variables bad?

I fail to see how it is "fail safe." If something were going to fail being set or passed as a paramater later it would certainly cause problems in the constructor, in terms of errors the constructor is the most volatile part of the object for error checking. Bloating the constructor with checking code is a bad idea anyway.

So how do you suggest to avoid crashing when someone "fails to pass something" as you suggest should be avoided? And in the example given, that something was to be passed to a constructor.

15. ### Why are static variables bad?

Personally I think this is a HUGE problem in that you code should not be designed in such a way that if you fail to pass something to it, that it crashes. It should if anything report it, or if it causes a fatal error it should crash with a thrown exception in a way that the programmer knows they messed up and it needs to be fixed immediately, rather than a user error.

The whole methodology behind the default constructor object is to treat the object as the most important thing in the world, that it should be concerned only with its own state and not trust any information received from other parts of the program, by verifying that data is both correct and exists it prevents the program from crashing without having to worry about things outside of its own code like "did the coder set this object right before creating me."

So what would be the correct approach in the example case, with the struct where a new member may be added? Where would the error be "reported" to, and in what way? More importantly, how would we know "whatever" was uninitialized, when its value as uninitialized may be undefined?

E.g.

FooContext fooContext;

fooContext.bla = <smth>; // old code that didn't know about the new "whatever" feature

// member whatever could have an undefined value, so how does this check that and "report" it, fail gracefully, etc.?

Foo *foo(new Foo(fooContext));

As like he says, it seems you need a constructor of some kind in fooContext to prevent this. Even if not one to force the programmer to pass a parameter, then at least a default one to initialize the variables so their values are all defined (perhaps so as to indicate special uninitialized states that Foo can then check for).

16. ### Map "areas"

However, what happens when a sector overlaps multiple areas?

17. ### Map "areas"

Usually I put a sparse container for such things.

Whatever it is, it's sorted into sectors which are quite a bit bigger than tiles (say 256x256 or 1000x1000 pixel for example). So everytime the player moves, I check the sectors the players bounding box is touching.

Simplest way for such a container is a std::map with sector pos as key and a list of trigger regions as values.

But doesn't this constrain the regions significantly? E.g. they must be a union of macro-tiles/sectors, no? And what do you mean "sector pos as key"? The number of each sector?

18. ### Map "areas"

Hi.

Suppose one has a 2D grid map for a game, and one wants to define special "areas" on the map, which could be bounded by a rectangle, ball, or polygon, and to which could be associated an effect or a name or something. I suppose one could store a list of these along with the level map, but what's the most efficient way then to find, given the player's position, which area(s) the player is in? How is this usually handled in games? Is the check performed every time the player moves?

19. ### Programming origin of (bug? feature?) in old game ("Duke Nukem 3D")

Apparently, I discovered something that said the kill-on-noclip was removed in version 1.4 and 1.5, the last of which is the version for which the released source code is for. So now I'm not so sure as to the meaning of the above code.

20. ### Programming origin of (bug? feature?) in old game ("Duke Nukem 3D")

I just got the code from the 3D Realms website and had a look. I believe your hypothesis is in fact correct.

I discovered the following code segment in the routine "processinput" in PLAYER.C:

    psect = p->cursectnum;
if(psect == -1) /* hypothesis: this means "out of range" sector */
{
if(s->extra > 0 && ud.clipping == 0) /* "clipping == 0" = no clipping? I note this variable is modified by the noclip cheat */
{
quickkill(p); /* kill the player */
spritesound(SQUISHED,pi);
}
psect = 0;
}


It looks to be exactly what you said. To check if the player is out of range, and kill them if that is the case. A failsafe, just as you thought.

There also appear to be a few other checks that look like this one.

Thanks for the suggestion!

21. ### Programming origin of (bug? feature?) in old game ("Duke Nukem 3D")

Well, if it's a feature, I suppose then one could find it by searching the source code for calls to the player death routine, no?

22. ### Programming origin of (bug? feature?) in old game ("Duke Nukem 3D")

Hi.

(I'm posting this here because to me it seems game-programming related, but if you think it should be elsewhere, you can move it)

I saw this on Wikipedia:

http://en.wikipedia.org/wiki/Noclip_mode

No-clipping can conflict with other elements of the game. For instance, in Duke Nukem 3D, and the Commander Keen series, having no-clip and walking outside the level area causes death, and if the player has god mode activated the game will be left in an infinite loop or crash due to the way god mode was implemented. In most source ports for Duke Nukem 3D, this problem is corrected and it instead behaves more like Doom.

I'm curious about this. Now, Duke Nukem 3D's source code has apparently been released under free license (GPL), so I suppose one could dig through it and/or run experiments, though I don't feel like doing it right now. What would cause this phenomenon (namely that going out of the level in "noclip" mode kills you), from a programming point of view? As it doesn't seem at first obvious that this kind of thing would occur.

23. ### Game loop question: how to solve this problem?

@SquaredD: "The inventory sub-state and the in-the-action sub-state can send commands to the ingame state to process." However, I thought that game states were supposed to be kept separate. But am I right in thinking this communication is OK in this sense since what we are doing here is building a _hierarchy_, and states on the lower level of the hierarchy (the sub-states) are not directly communicating with each other, but are instead communicating with the states on the higher levels of the hierarchy, and so the coupling of sub-states is loose and not tight?

Also, do the sub-states contain their own loop or just render/logic/input (or just render/logic only?) functions? If just those functions only, then it still doesn't seem to solve the problem of suppressing the input for the loop cycle performed while in the "game action" substate that immediately follows the ending of the "inventory" substate when processing drop commands (since the logic for that cycle is not using new input, but rather completing a command in progress).

24. ### Game loop question: how to solve this problem?

Depending on the game style, whether realtime, turnbased, multiplayer I can see lots of possibilities for resolution. I think the second option Matais presented would be the cleanest.

while(running)
{
//Process input.
//process events
// update logic
// render
}


So user presses d, the input is processed, a state change is requested, the rest of the logic is handled, and the scene is rendered. on the next iteration, the menustate allows the user to select the item for dropping, the scene is rendered again, and we return to the gamestate. on the next iteration, we now have an event to process(user dropped itemx) so we handle it. process the rest of the logic, and render our 3rd frame.

However, there's the problem: "a state change is requested, the rest of the logic is handled..." -- but we shouldn't do a turn's worth of logic until after we get the item to drop, since the drop happens as part of that turn. And also "on the next [3rd] iteration, we now have an event to process"... but on that iteration, before we get to "handle events", we go through "process input"... yet we shouldn't process more input until we have finished the drop.

25. ### Game loop question: how to solve this problem?

OK, maybe my explanation wasn't quite good. I wrote my post kind of hurriedly. Hopefully this is better:

The loop would look like (pseudocode) (note this loop is for a simple "text mode" roguelike with no continuous animations, etc. -- that would require a different kind of loop that runs many times per second):

while continuing: // 1 cycle = 1 turn in "playing" state
input = inputSystem.getInput();
gameState.logic(input);
gameState.render();


The state changes happen at the end. Consider what happens in the loop when one presses a "d", for "drop item", say. The input system gets the "d" key press. This then goes on to the logic _for that game turn_. However, _we cannot complete the command without first getting a choice of item to drop from the inventory menu_. So, we must:

1. defer the logic for the rest of the turn (move monsters, etc.) until the menu completes

2. switch to the menu state

3. when the menu gets its input, switch back to the game state.

4. finish processing the command and handle the logic for the turn.

Now, assuming the state transitions happen at the end of the loop, consider what happens in (3). The loop completes its final cycle in "menu" state, then switches back to "playing" state. But our work is not done -- we still need to do step (4). Yet when the loop executes its next cycle, now back in "playing" state again, it goes to requesting input again, when it should go to finishing up the logic for the turn. And the logic function will start all over again from its beginning, with a new input... what happened to finishing up the command we wanted to do (drop the item), and handling the remaining logic that would follow it in the turn?