Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 13 Jul 2003
Offline Last Active Sep 23 2016 07:14 PM

#5310267 (2D) Handling large number of game objects, no quadtree

Posted by on 10 September 2016 - 12:31 PM

A grid is a tried and true very simple method. Whatever sized your world is, split it into evenly spaced grid cells and then based on where the viewer is in the world, it's super trivial to calculate the min and max bounding extents of the grid to isolate the small subset of objects that are relevant to where the camera is looking.

#5173201 Crashes When Character Walks

Posted by on 12 August 2014 - 04:47 PM

What's the value of gPlayer.CurrentFrame when it crashes? Go over the values of all your variables in the debugger when it bombs and you should get a hint.

#5118482 How to split up pathfinding? How to implement divide-and-conquer on pathfinding?

Posted by on 20 December 2013 - 08:48 PM

I work with huge terrains and navigation meshes. We can't even build the entire navmesh due to memory constraints(it uses the popular voxellization techniques), so we built the navmesh in tiles. In order to facilitate long distance pathfinding, which would be extremely slow for long paths, I use the resolution of these tiles as part of the hierarchial pathfinding, which I recommend you do here as well. it's much simpler with tile maps.


The idea is just to group your navigation into larger tiles, and then build a higher level graph on this information. You can do it with a higher level grid or create tile groupings.





Depending on the size and complexity of the map, this can simplify the pathfinding hugely. Pathfinding could boil down to a simple search inside the region you are in, and once the search hits the high level sector border, it can skip entirely over all sectors in between, using the cached connectivity of the high level graph. Once it reaches the destination sector, it can fall back down to the tile grid for the rest of the path. Once you have that path through, which includes a mix of high and low level paths, the high level edges would need to be filled in for each tile, but this can be done incrementally as you follow the path. I ended up not doing incremental updates though, because it caused problems such as not having enough path context into the future in order to do my string pulling properly, so I ended up building out the whole path by the time I returned it, but the multi-level pathing is still a huge performance improvement, and filling in those high level sectors is basically a flood fill from the starting polygon/tile until it reaches the next expected high level tile.

#5118118 Pathfinding with virtual fields

Posted by on 19 December 2013 - 08:02 AM

First thing is to render the vector directions at each node. Whether those look correct or not will narrow down where the problem is.

#5117880 Are there alternative methods of obtaining neighboring nodes of a node from a...

Posted by on 18 December 2013 - 10:16 AM

The navigator subclass, such as the NavigatorNavmesh, is indeed tied to the navigation mesh. It's an implementation of my interface where it is tied closely to how the navigation mesh stores data. The Navigator is my path finder and my path smoother. This object serves several purposes for me. It represents the state of navigation for a particular entity. The navigators could be updated from multiple threads, modifying their internal search state and referencing the navigation mesh in a read only manner, they could be updated serially in a time spliced sort of manner(allowing many paths to be in progress simultaneously), and it shields the rest of the code from the choice of navigation system I'm using, allowing me to change it easier at a later point. Also, since it maintains its own internal state which may involve functionality closely related to the navigation system, it can handle the dynamic aspects of path following was well, such as string pulling, often implemented in a way that requires regular maintenance of the path which can be encapsulated in the navigator.


You don't have to do it this way. You can just create a function on your map class or something if you want to start simple that solves a path and gives you back an immediate result in the form of filling in a result object or a list of path nodes, etc.


Status TileMap::FindPath( PathResult & resultOut, const vec2 & src, const vec2 & dst, ... );


Path nodes hold the state of the navigation query at a particular state, the code, the parent pointer for reconstructing the path when the goal is found, etc. This is temporary scratch data and doesn't belong in the same objects as your Tiles, which presumably hold a reference to the image used for that tile, whether the tile is solid or not. I think about the tile map in a 2d game as an image, and the tiles as the pixels of the image, the color channels as the data about those tiles. I would not bloat that data with pathfinding search state. Other than bloat, if the tile map, of which there is presumably only 1 copy of, contains the search state, you can only solve for 1 query at a time.


I would suggest, even if you keep it as a simple function call for an immediate path solution and nothing fancy like a navigator, that you keep the search state separate from the tiles.


something like

struct PathNode
    int x,y; // coordinate of node in tile map

    // search state
    PathNode * mParent;
    float g, f;

#5117840 Are there alternative methods of obtaining neighboring nodes of a node from a...

Posted by on 18 December 2013 - 08:15 AM

I just mean the tiles themselves don't need to know the object they are contained in. I wouldn't advocate trying to take the functionality entirely out to a standalone method.


I may have partially misunderstood. Are you talking about the pathing nodes used during a path search or the tile nodes of the tile map?


I don't think the tiles of the tile map should need a pointer to the map, or know their location within the map. For pathfinding purposes, the 'PathNode' needs something that maps back to its location in the map so that it can expand the search at each iteration, but that can be properties specific to the PathNode and not the TileNode. That is, assuming you are not using the tile nodes directly in the pathfinding, which I would not recommend, since the pathfinding needs a set of data specific to the search that has no reason to be persistent with the tiles(g cost, f cost, parent pointer, etc).


I tend to write standalone objects as interfaces to pathfinding that are allocated per AI that are basically their navigation interface.


// for each AI

Navigator * nav = navmesh->AllocPathQuery();

nav->FindPathToGoal( pos, myCapabilities );


// incremental updates for tim splicing

switch( nav->UpdateSearchStatus() )


case PathFound:


    // get the string pulled corners

    NavCorner corners[4];

    const size_t numCorners = nav->GetNextCornersInPath( corners, 4 );

    if ( numCorners == 0 )




    // update AI steering/velocity with the corners



case PathNotFound:

    // print error, etc


case PathSearching:





I usually allocate it through the specific pathfinding system and it maintains a reference to the data classes it needs to function. I've also had good luck abstracting these Navigators around the concept of 'corners'. A base Navigator class can take and provide access to a generalized representation of the path, while several implementation subclasses may be available for different navigation systems NavigatorTileMap, NavigatorNavMesh, NavigatorWaypointGraph, etc. In all these cases, the specifics of the pathfinding and interaction with the specific navigation system can be contained in these subclasses while the interface provides general access to the string pulled corners of the path, with edge flags and node flags that communicate information about the underlying path, such as the types of polygons and such traversed.

#5117668 Are there alternative methods of obtaining neighboring nodes of a node from a...

Posted by on 17 December 2013 - 02:54 PM

I would suggest not storing a reference to the map or storing the tile coordinate in the tile. The map should be the one doing all the logic so individual tiles should only be a tiny set of data.

#5111890 Component Based Entity Design communication between components and systems

Posted by on 25 November 2013 - 11:34 AM




In my opinion systems will 'update' the components they are responsible for updating directly, though if you prefer your update event can accomplish the same thing. An InputSystem will update all the known InputComponents. That might include PlayerInput components(possible multiple for local multiplayer), and AIInput if you implement your AI to function through the same control interface. Each instance of PlayerInput will know about what keys/controllers are relevant to that particular player and interpret it accordingly.


I have one thing that I want to be sure 100%. In the system you provided, ideally, systems store components for their specific types. So, GraphicsSystem stores GraphicsComponents; PhysicsSystem will store PhysicsComponents; etc. Do I understand it correctly?



Yes basically. Although a system might also be responsible for managing/updating multiple component types. TriggerComponent might also be managed by the PhysicsSystem since it might involve the underlying physics system for detection of the triggering. Point being it doesn't need to be a 1 system to 1 component mapping. Some components may not even have systems, they may be book keeping or functionality components used by other components.


If the component knows which buttons map to which actions, it can speak to the relevant components directly.


What if we don't have the component? Is there a way to make this system modular rather than tightly integrated? Or there is always going to be integration between systems no matter what?


I like the physics system approach a a lot, even though I don't like the idea of every component being connected to each other. I need to find a way to adapt this system to my beliefs tongue.png I will post it here the moment I find it.


If you don't have the component to talk directly to? I would detect that during object initialization. The nature of a component system always ends up as a bunch of components with various dependencies on each other. Avoid it when you can but taken too far it can adversely affect the system. A PlayerComponent and AIComponent probably depend on a CharacterComponent, or at least some component that implements an interface of that expected type. To me this is an error condition better handled as a data validation step rather than a runtime error condition as much as possible.


In my opinion there is always going to be a coupling between components. I'm not personally very convinced that a message passing system provides much benefit. In the end you are still doing similar things. Calling a function(sending an event by name or Id), passing arguments(as event parameters), and possibly relying on a result by the handler(the return value). The key difference IMO is that with an event system that functionality is obfuscated by the generic interface required of a general purpose event system. It is opened to being handled by unexpected components in unexpected ways, maybe being restricted in what types of data it can send, unless you dynamically new event objects and pass the parameters that way and rely on casting. In the end the data contained in these events is not much less of a coupling than a direct call, other than the need to have components know of the other component, or at least know of the interface to another component family. As a function call, changing that 'contract' between the 2 components(the parameters of the data passed, and the return value) is simpler to do, as it is just a function parameter changes, and the compiler will help you avoid making mistakes at callsites, mistakes that may be easier to slip through with a general purpose event system, depending on implementation.


All that said, to event or not to event is partially a subjective judgement, so there may be other reasons to prefer that method, or a mix of events and direct communication. Most of my initial reply as far as structuring the components is still relevant whether you use direct communication or event based.

#5111838 Component Based Entity Design communication between components and systems

Posted by on 25 November 2013 - 08:21 AM

Components and systems know nothing about each other.


I can understand components not knowing about systems, but I don't see why you would have systems not know about components. It is the whole point of systems to handle the processing of components relevant to those systems. Some people might argue that making things event driven in this way is better, but I'm not a big fan of event systems used in this way.


In my opinion systems will 'update' the components they are responsible for updating directly, though if you prefer your update event can accomplish the same thing. An InputSystem will update all the known InputComponents. That might include PlayerInput components(possible multiple for local multiplayer), and AIInput if you implement your AI to function through the same control interface. Each instance of PlayerInput will know about what keys/controllers are relevant to that particular player and interpret it accordingly.


There isn't really a single correct way to implement all you describe. There are a bunch of different approaches that may have pros and cons. I'll try to explain an alternative component implementation that I feel makes more sense.


Your motion appears to be implemented in full tile increments, but even in that situation I would design the component system with an implementation that is more appropriate to being used if you were using incremental motion, with a real collision system. The tile increment motion can be hidden away inside the implementation details.


For example.


PhysicsSystem - knows about and updates PhysicsComponents, resolves all physics based on velocities/forces applied to the PhysicsComponents

PhysicsSystemTile - specific implementation for your full tile locomotion, moves each object the most appropriate direction to their velocity a full tile size

PhysicsComponent - simply holds the velocity/force accumulations to be applied by the physics system and resolved with others.

PlayerInput - interprets control input and sets velocity



The benefit is of course that not only are you future proofing for the flexibility of doing a proper say box2d physics version of the game, but you are reducing the component cross chatter.


If one types 'w', the input fires event "moveUp"; the fired event is sent to a the entity with the PlayerComponent


This event is unnecessary. The specifics of which keys to interpret as which actions should be properties of the specific Input component instance. Again this reduces component chatter and leaves the game open to multiple player instances each deriving input from separate sources, ie local multiplayer.


The entity passes the "moveUp" event to all the components.


Again this is unnecessary chatter. Event broadcasting IMO is a dirty temptation of event systems. If the component knows which buttons map to which actions, it can speak to the relevant components directly.


TilePositionComponent receives it, and sends an event "updatePosition(currentX, currentY, currentX, currentY-1)" to TileLevelSystem.
    TileLevelSystem sends event "isPassable" to an entity in the new position (if there is one); if the event returns true, the player moves to the new position and the "updatePosition" event returns true. Then the TilePositionComponent's currentX and currentY gets updated.
    Then everything gets rendered.


These details are highly specific to your specific motion model, and would need to be wholly replaced with the introduction of a physics system. It may even be problematic to implement simple animation/lerping the entities to the center of each tile.


If instead we adopted the PhysicsSystem approach, The PlayerInput would interpret the input keys into a velocity, The PhysicsSystemTile would take that velocity and for example use the most significant direction to animate/lerp the PhysicsComponent it processes to the next valid tile in that direction. For managing crossable and uncrossable tiles, do that the same as you would if you were using a physics system. Collision masks. The PhysicsSystemTile is now the only place that has to know or care about the fact that your game operates at the tile level in terms of locomotion, and if you want to change that system in the future it becomes very simple. The most important short term win though is the reduction in component cross talk and the dependencies that introduces. The relationship between Input, Physics, and motion I think is one of the easiest aspects of a component system to keep pretty separated. Certain input ultimately gets mapped to velocity. Other input gets mapped to actions, probably on the PlayerComponent or possibly a more general CharacterComponent if you want the AI to function through the same interface. Many games, and all bots for FPS games operate like this. The AI ultimately feeds 'button presses' that maps to specific action into the game so the AI can operate through much the same code path as players. The analog in a component system might be that the AIComponent ultimately sets 'action' flags on the CharacterComponent, the same as a PlayerComponent.

character->SetAction( true, FL_ATTACK );

For item picking, I would probably again utilize some knowledge about how it would likely be implemented in a game with a physics sytem. Pickupable items would probably have PhysicsComponents that utilize a non collidable pickup trigger mask. This would make it the responsibility of the PhysicsSystem when it is updating entities based on their motion, to maintain a list of items the character entity is 'touching'. In a fleshed out game, the knowledge that a player is touching a pickable item might be reflected in rendering button prompts on the GUI. The PlayerComponent would probably have some specific knowledge about what to do/present whenever his physics component is touching pickable items.


Maybe something like this

    PhysicsComponent * physics = GetEntity()->GetPhysics();
    Entity * pickable = GetFirstPickable( physics->GetTouchedEntities() ); // local function that gets the first pickable in the list(may be multiple), distinguished by collision mask or presence of certain dependent component
    if ( pickable )
        EnablePickupGui( pickable ); // shows a gui for the current pickable
        if ( GetInput( IN_PICKUP ) )
            PickupItem( pickable );

#5108474 Is hacky code allowed in industry?

Posted by on 11 November 2013 - 09:00 AM

I tend to think about implementation details in terms of the mechanics of the game. Your example suggests a mario clone sort of block triggering powerups. From that perspective, you need to first think about what the mechanism for triggering the blocks is going to be. Simply colliding with the blocks is too low level of a mechanism with which to trigger the spawning of the powerup. You want mario to trigger the powerup when he jumps upward into the block and collides, and also if the game has the power drop thing that allows you to smash down from a jump with it. Because the triggering of the blocks should be dependent on the type of action that is being performed, it would make more sense to generalize these activities within the state inside the Mario object class, such that when you jump up into something, or smash down onto something, you are calling functions that provide that context, and the objects being hit can respond accordingly.


Some example pseudocode

enum HitFeedback

class Mario : public GameObject
    void collide( collisionevent )
        HitFeedback hit = FEEDBACK_HIT;

        // assuming -z is down
        if ( collisionevent.normal.z < 0.5 ) // did we jump up into the object?
            hit = collisionevent.otherObject.HeadSmashed( this );
        else if ( collisionevent.normal.z > 0.5  && IsSmashingDown()  ) // did we fall down into the object in the smash down state?
            hit = collisionevent.otherObject.SmashDown( this );

        if ( hit == FEEDBACK_HIT )
        // handle landing on slopes or ground to change state to walking, etc
        if ( hit == FEEDBACK_NOHIT )
        // allow the character to continue its current physics state, if flying, keep flying, if smashing, keep smashing

// Then your various other game objects can easily implement responses to the game mechanics available by your player

class BreakableBlock : public GameObject
    void HeadSmashed( Mario & player )
        return FEEDBACK_HIT;
    void SmashDown( Mario & player )
        return FEEDBACK_NOHIT; // so that mario can continue smashing down a column of breakable blocks

class PowerupBlock : public GameObject
    void HeadSmashed( Mario & player )
        // implemented via a state as it likely involves playing an animation and isnt just an immediate spawning of the powerup
        ChangeState( SPAWN_POWERUP );
        return FEEDBACK_HIT;
    void SmashDown( Mario & player )
        ChangeState( SPAWN_POWERUP );
        return FEEDBACK_HIT;
class CoinBlock : public GameObject
    void HeadSmashed( Mario & player )
        if ( mCoinsRemaining > 0 )
            player.AddEvent( AddCoin( 1 );
            if ( mCoinsRemaining <= 0 )
                ChangeState( DEACTIVATED ); // animate, disable callbacks, etc
        return FEEDBACK_HIT;
    void SmashDown( Mario & player )
        // same action as HeadSmashed
        return HeadSmashed( player );

class Turtle : public GameObject
    void HeadSmashed( Mario & player )
        // hitting a turle from below is damaging, and should probably be treated as solid
        player.AddEvent( Damage( 1 ) );
        return FEEDBACK_HIT;
    void SmashDown( Mario & player )
        ChangeState( FLIPPED_OVER );
        // add some small velocity so the turle gets knocked to the side a bit from where mario smashed down
        return FEEDBACK_NOHIT; // so that mario can continue smashing down to the ground

Implement things with respect to game mechanics, and not so much the low level functionality of collision, physics, sound. Those low level systems will often be intricately tied to the function of certain mechanics. In marios case there will be some degree of complexity in interpreting the physics and collision information into a way that gets the actual game mechanics working as you want, but most of those details would ideally be encapsulated into the objects where it matters, such as your Mario class in a simple implementation. The game objects can provide some amount of hit information back from its callbacks such as in this case, so that the type of object can propagate back and effect

#5094053 Wander behaviour in 3D

Posted by on 14 September 2013 - 01:11 PM

This sounds possibly similar to the behaviors I made for the hostile boats in the Mercenaries 2 game. For that we needed boats that chase the player boat or some other target, which could also be the player flying over in a helicopter. I ended up implementing a simple behavior that was applicable and pretty good looking that applied to both.


Basically the boat AI would just seek to the nearest tangent position on a circle around the target. If the target was stationary, this simple behavior would cause them to drive in a circle around the target position, which was great because the guns on the boats, which were mostly able to shoot out the side of their boat, would continue to be able to shoot. If the target was moving, it meant the boat would give chase in such a way that they would be attempting to drive up along side the player, which is a nicer looking behavior than the boat trying to drive directly at the player. If the player cut across their path, they would pick up chase on the other side of your boat, as that would then be the 'nearest' tangent position.


This would seem to me a similar behavior potentially for a bird, as they tend to circle areas, especially birds of prey. I would treat the vertical element in a drifing sort of fashion. Allow the altitude to change randomly or with a sort of wander steering behavior where it may drift up and down. The behavior can be adapted when you want them to seek more directly to a target by zeroing out the circle radius. You could also apply a drifting value to the circle radius to add some 'noise' to both the circling behavior and the tangent offset points, which may allow it to look a bit more random and bird like and not so exacting and direct.


Then you can give them random points around the game world as waypoints to visit, and they would seek to each based the nearest tangent offset which would drift as the radius of the circle drifts, and it's even more useful if you want a bird to give chase to another dynamic entity or give them paths through the player position and they would fly not directly over the player but at an offset that makes them more visible and provides circling behavior all in one.


It's simplistic and isn't a full bird modelling technique, so it depends on what fidelity one is going to be observing whether it will fit your needs.

#5092757 Pathfinding on 7 oceans

Posted by on 09 September 2013 - 11:11 AM

The complex solution to this type of problem as alluded to is to implement a hierarchy within the structure of the pathfinding so that A* doesn't search through that many nodes. If you take the globe and partition it into a lower resolution polar grid, and then associate each of the high detail nodes into those 'buckets', you can create a hierarchy for the pathfinder that will dramatically reduce the complexity of calculating the path.


As an alternative, depending on your requirements, for that many nodes, it would only be about 25MB to store a lookup table for pathfinding, if the pathfinding requirements don't need to include dynamic weighting. If weighting needs to change dynamically it gets complex with having to update the lookup table.


As another alternative. If the goal node changes infrequently, or especially if there are many units moving to shared destinations, it might be faster and easier to implement if you flood fill from the destination node to generate an influence map that the ships can simply follow the decreasing weighted edges until they reach the destination. I've experimented with good results of essentially pathfinding on influence maps like this by flooding weight values. Since the flood isn't so branch and condition heavy as a full path query, building and updating the layers are actually very fast and cache friendly, and once you have the influence map, pathfinding is just a lookup and a follow into the best weighted neighbor.

#5087955 Determining effect order

Posted by on 21 August 2013 - 06:13 PM

I would probably simplify the effects so that you can put together discreet stages of effect modifications where the order doesn't matter, ie so the math is communative and easy to understand, sort of a series of accumulations and applications in stages. The key I think is a sensible ordering of the calculations with an ordering that makes sense to the player.


For example.

  1. Take input list of effects, such as list of damage types
  2. Transform effect types to other effects so they will be treated as though they are the transformed effect
  3. Accumulate all damage together, keeping them separated by type still(fire, arcane, magic, physical, etc), you can also accumulate healing effects as well during this loop.
  4. Apply healing modification effects to healing values.
  5. Apply total healing to the character so that the healing comes before the damage to offset the damage if you so desire. Alternately you could split healing effects into pre-heal and post-heal to modify this order for certain cases, or treat post heals as tiny delay/duration regeneration.
  6. With the accumulated damage per type, apply damage modifiers that apply to each type, (fire resistance will reduce the fire damage only, etc)
  7. Accumulate damage modifiers together and apply them to the characters health.


If I were building an effect heavy system I would probably treat everything as an effect that goes through this pipeline. It wouldn't be just the spell effects that go through this, but also the protection levels of armor would be represented as an effect on the list.


Start with something simple and easy to follow and worry about the complex order issues when you actually run into a problem creating an effect that maybe you can't with this. At that point it will be easier to understand what and where you have to plug in some new 'features' to get what you need.

#5087073 Determining effect order

Posted by on 18 August 2013 - 11:24 AM

I would create dependency categories that you can associate with effects that require ordering dependencies. This allows your effect to define one or more types of effects it depends on being processed first so that when effects are added or removed you can order them by their dependencies. Dependencies could vary by specificity. Maybe there is a damage dependency that must process after all damage and more specific ones that only apply to fire damage. Depending on the complexity of the effects system you might need to essentially build an effect dependency graph with the prerequisite conditions and then when taking damage that may have multiple effects, propagate the list of damage effects through the tree, where its effects might split and follow different paths down the graph and get modified in various ways until it comes out the other side of the graph potentially heavily modified or transformed into a wholly different effect set.

On top of that you might also want to create processing groups to batch process different effect types before others. Effects that convert effects to other effects should probably come first so that before other effects are applied, conversions are made so that later effects can be applied to the conversions.

#5084376 AABB Tree dEMO

Posted by on 09 August 2013 - 06:31 AM

The coolness would probably come from the visualization. Render the tree in a window and have options to do a query with and without the help of the tree and maybe print out the performance results in both time taken(versus a linear search), and the number of AABB tested. That would be a cool app to illustrate the point of such spatial queries.