# Question
Title: Why do people like `realistic' physics and graphics in games?
If games are all about *fun*, then why do people tend to like realistic physics and graphics are good for games?

Can you cite your source?

# Answer
(warning, controversy approaches)

First of all, how do you define "fun?" Until you can supply us with a universally accepted definition then your very question is itself unanswerable...

I'm not going to cite sources, do your own homework =P

I'm also going to skip past the part where you bias the question by assuming that physics are not fun and are trying to get a negative proof.

But here's the deal for physics.

1) People like internally consistent behaviors in their games, using a realistic physics model is a direct way to give players that consistency.

2) Since stuff does what you'd expect it to in a physical universe you don't have to teach them how to play, leading to a comforting sense of competency.

3) Physics as a game play model is still relatively new and therefore it's entertaining because of the novelty of it.

4) Emergent behaviors evoke a sense of wonder, exploration and experimentation is rewarded, and again the novelty aspect arises.

5) Is any of that "fun?" I don't know. It just is.

And here's the deal for graphics.

I posit that graphics have absolute **nothing** to do with fun. Graphics do, on the other hand, have a lot to do with enjoyment and whether a player likes a game or not.
> 12 votes

# Answer
It isn't about realism or not.

It's about fulfilling a desire for the player.

What you see is that the strive towards "more realism" is simply by trying to put the player closer to the place that they want to be.

So you get better texturing, lighting, physics, etc. is all towards putting the player more into the suspension of disbelief.

Now that being said, it isn't exactly about what's "real", but what people "expect". A perfect example of this is the weapons in Modern Warfare. The guns do not behave at all like they do in "real life", but they behave almost *exactly* like people are used to seeing them in movies. So when they get a particular gun in their hands and fire it off, it feels "real" in the context of their knowledge.
> 12 votes

# Answer
Speaking only of the physics side of things, an advantage that realistic physics in games have over "cartoon" or made-up physics is that the player intuitively has a feel for how things behave in the real world and can easily transfer that into game scenarios. This makes games with realistic physics more approachable and easier to pick up and play. There is no need to learn how the world will respond to an action if the player already has a good idea of how that same scenario would play out in response the real world. The less time a player has to invest in learning new/strange physics the more time they will have to actually play and enjoy the game, so that may be a part of the answer.
> 4 votes

# Answer
People don't actually like realistic physics and graphics in games.

People **say** they like realistic physics and graphics. But the games they point at as examples aren't actually realistic at all; they just have fancy shaders and licensed Havok (or some other simplistic physics middleware).

I think you'd be hard pressed to find a game which provided **either** realistic physics **or** realistic graphics, apart from those FMV adventures which were being produced back in the early 90s. And you saw how much people loved those.

Everything's stylised and optimised and simplified in video games. Nothing's actually "realistic".
> 4 votes

# Answer
The realism of graphics and physics adds to the immersion of the game, but physics and graphics do not have to be held to a realistic standard.

Fun is not directly associated with realism. Part of what makes a game fun is giving the player a good sense of empowerment. This requires a balanced set of physics rules to be able to do a lot of cool stuff as if it's second nature.

High-profile games are usually held to the standard of summer action Hollywood movies, and from a technical standpoint this actually isn't too bad. Those movies are pretty liberal with physics and visual effects and filled with over-the-top action sequences that only the hardcore engineers and physics geeks will have trouble accepting.

You just need enough realism to that degree to satisfy the average gamer, and they'll be pulled into the game's world. On the other hand, glitches are a sure way to remove you from the immersion and remind you that you're still just playing a game.

Only sim-type games try to make the exception and aim for a true-to-life feel. Case in point, sports and racing games for the serious fans.
> 2 votes

# Answer
Your physics don't need to be realistic to be more enjoyable - there have been a few games with unrealistic physics (for example in Prey you could shrink and control gravity); however they were *realistic within the universe described by that game*. Another good example of unrealistic physics is space simulators: flying a space craft is actually really tricky business; however they really dumb down the physics for the player - so that they can have dogfights without having to fight with the physics at the same the time. If you can logically explain the physical constraints of your universe (and keep them enjoyable) any player will happily accept them.

Physics, just like the graphics and sound, are a form of escapism. People play games to escape the constraints of reality; games with realistic physics sometimes do some pretty crazy things (that you would never attempt in real life).

With all that being said, the reason that games with realistic physics (according to our universe) are enjoyable to players is because the game so happens to be set in our universe; and therefore the physics are believable - and don't get in the way of the player (because they already know how to interact within those physical constraints).

Your first priority with any game component is to make sure it enhances the enjoyability of the game. If that means your physics need to be realistic; then make them realistic.
> 2 votes

# Answer
Personally I like games to be as realistic as possible, to the point of actually being boring. For example I love EU3 because it is more of a simulation than it is a game. That being said sometimes I like to play a more 'mindless' game that doesn't resemble any part of reality, as I know it. There should be all kind of games for different kind of people, but to say that realistic games aren't fun is false. When you take something like History, and create a game that doesn't depict the time realistically, it really ruins the game for me regardless of whether the game is fun or not because each time I see an inaccuracy I am instantly reminded that this isn't the period I had thought but rather a fictional story based on history. The more realistic the game, in certain circumstances, the better it is.
> 2 votes

# Answer
> If games are all about fun, then why do people tend to like realistic physics and graphics are good for games?

I don't like realistic graphics and physics for games so much so I'll just jump in to be weird. For example, I don't think Super Mario would be better with realistic graphics and physics instead of cartoony graphics and hard-coded magic numbers where the designers focused more on making the game as responsive and as smooth to control as possible instead of realistic.

So I wanna vote for less realism in games! And how about small worlds? What's up with this big open world craze? I like a world to only be as big as it has interesting content, like unique NPCs with really fleshed out backstories and personalities to talk with. My limit for scale vs. interest balance was like Ultima 7. I don't want miles and miles of trees and mountains. I get bored walking through and riding through that stuff. Most of the time when the game has a huge world, I wanna skip through 99% of it, as with Fallout 1 & 2 which had an overworld screen and it didn't even bother with letting you walk through miles and miles of desert. The exception is for game engines so fun where any part of the world is so amusing just to goof around in, like Grand Theft Auto which, in spite of having lots of repetitive content, is damned fun to just play in some aimless way. That said, I still liked Vice City the most and that had the smallest game map, and even the biggest GTA maps aren't that huge. A whole lot of interesting content can be packed in a small but dense world. It doesn't have to be scattered and made sparsely distributed between miles and miles of wilderness to the point where the player is spending more time walking than doing interesting things.

That said, sometimes realism adds a new element of control and that's where I like it. For example, some types of games using more sophisticated (not sure I'd say "realistic") physics become amusing because they offer a greater deal of interactivity when you can toss ragdolls around and shoot like a pillar and a whole building collapses killing all the enemies inside while one of them catches on fire and starts screaming and running towards water while yelling for help which is really funny. There the game is offering a whole new element of control and interactivity not seen before, and I do like having lotsa control and interactivity in certain games. Sometimes the physics opens up a whole new type of game genre, like those games where you have to carefully stack things without them falling down.

But I do think realism is totally overrated when it's pursued just for its own sake. I would rather see it applied in a discretionary fashion and tastefully for things that are genuinely fun, like using physics to simulate bouncing boobs. There should be at least 2 or 3 CPU threads dedicated to doing that for every game and you only really need 1 thread for the rest of the physics.

> Can you cite your source?

-- DrunkCoder 2018
> 1 votes

# Answer
Realistic physics and graphics are good for a game **if the game relies on realism to effectively engage the player.**

Consider a game, or series, such as Forza. Forza's aim is to bring the player to a world in which they are driving a high-performance car around famous circuits attempting to break existing records and establish their career as a driver. To facilitate this aim, realism is extraordinarily necessary. Simulating a car's engine, tires, tuning, and handling, as well as track conditions and environmental conditions are clear choices when considering what will help add to the player experience, given the game's aim.

It would be difficult to determine exactly why people are drawn to titles that offer realism, but I think an argument could be made that a major factor is the rapid advance of technology over the past few decades. There's always a great interest in "what's next," so given how quickly technology advanced, we always look for something better, and it happens that realism quickly got on the radar. Graphics are physics are what we focus on most likely because they are much more quantifiable and easily defined than fun or gameplay.
> 0 votes

---
Tags: physics, non-photorealistic
---


# Question
Title: Object pools for efficient resource management
How can I avoid using default new() to create each object?

My previous demo had very unpleasant framerate hiccups during dynamic memory allocations (usually, when arrays are resized), and creating lots of small objects which often contain one pointer to some DirectX resource seems like an awful lot of waste.

I'm thinking about:

1. Creating a master look-up table to refer to objects by handles (for safety & ease of serialization), much like EntityList in source engine
2. Creating a templated object pool, which will store items contiguously (more cache-friendly, fast iteration, etc.) and the stored elements will be accessed (by external systems) via the global lookup table.

The object pool will use the swap-with-last trick for fast removal (it will invoke the object's ~destructor first) and will update the corresponding indices in the global table accordingly (when growing/shrinking/moving elements). The elements will be copied via plain `memcpy()`.

Is it a good idea? Will it be safe to store objects of non-POD types (e.g. pointers, vtable) in such containers?

Related post: Dynamic Memory Allocation and Memory Management

# Answer
> 6 votes
Memory pools or object pools are a very common practice in game programming. Another common practice in console games is to allocate everything in module-specific pools to "budget" memory and have precise control over when and where allocation occurs.

Some years ago I asked advice on which strategy to go with a game I was making: https://stackoverflow.com/questions/1964722/one-big-pool-or-several-type-specific-pools

The strategy to use is mostly dependant on your game but anyway, making sure no allocation/deallocation is being done while the game is running is a golden rule of thumb. It can be broken if the game state might vary depending on external informations, like when you work on MMO games. But then, having memory pools for several categories of size of objects (instead of pool of objects) might be a good idea to keep the memory as stable as possible.

Pooling should work for any kind of object, depending on the strategy. What's important is that the full type is known by the pool to allocate enough memory, then do whatever you want with the object. The other thing to not forget is to let the pool know when the object can be released to be used later (without deallocating it's memory).

# Answer
> 2 votes
```
The elements will be copied via plain memcpy().

```

And... when you come to apply this to your `Text` objects? Never, ever, use `memcpy` when you can use `std::copy`.

Your intended goal is laudable but your implementation details seem more than a little sketchy to me. Boost comes with a pre-built pool allocator you can use which likely put a lot more thought and time into this than you did, and works for any type.

# Answer
> 2 votes
For C++ an "object pool" makes little sense, since you have the ability to construct and destroy objects without allocating and freeing memory with placement new and manual invocations of a dtor. "Memory pools" make more sense \*.

> * Note that I distinguish "object pool" from certain types of "resource pools" like thread pools. Thread pools aren't intended to save the cost of allocating and destroying a thread handle's memory. They pool threads in order to avoid the operating-system level cost of repeatedly creating and destroying threads. Those types of resource pools make sense in *any* language, but I wouldn't call them "object pools" since that term is often reserved for use cases where objects are deliberately kept reachable to avoid GC overhead.

Here your best bet is probably a simple free list for each type of object you allocate if you genuinely have heap allocation/deallocation-related hotspots (along with some additional page faults and cache misses). A free list exploits the fact that all the memory it pools is going to be pooled in the same-sized chunks which is going to be sufficient if you use a separate free list for each object type or subtype you'll be allocating and freeing. It's not a variable-sized allocator. It returns a fixed-size amount of memory for the client to use each time.

Here's a basic free list to get you started. I didn't bother to make it thread-safe and generally you'd probably want to use these locally for a given thread anyway if you're suffering allocation/freeing-related bottlenecks since this implementation, at least on my machine, is about 20 times faster than `malloc/free` but it slows down to being only twice as fast as `malloc/free` the moment you involve a completely uncontended spin lock. I also didn't bother with exception-safety if `new` fails in the code below, though I don't think it's worth bothering in a game context (but you can if you want with a little more work or if you don't mind paying for the overhead of using `std::vector` and `std::list` which require a little more memory for size and capacity and so forth in exchange for proper reversal of side effects on `std::bad_alloc`).

```
#ifndef FIXED_ALLOCATOR_HPP
#define FIXED_ALLOCATOR_HPP

class FixedAllocator
{
public:
    /// Creates a fixed allocator with the specified type and block size.
    explicit FixedAllocator(int type_size, int block_size = 2048);

    /// Destroys the allocator.
    ~FixedAllocator();

    /// @return A pointer to a newly allocated chunk.
    void* allocate();

    /// Frees the specified chunk.
    void deallocate(void* mem);

private:
    struct Block;
    struct FreeElement;

    FreeElement* free_element;
    Block* head;
    int type_size;
    int num_block_elements;
};

#endif

#include "FixedAllocator.hpp"
#include <cstdlib>

struct FixedAllocator::FreeElement
{
    // Allocated chunks serve as a singly-linked list node when free,
    // client data when used.
    FreeElement* next_element;
};

struct FixedAllocator::Block
{
    // Blocks are linked together as singly-linked lists, pooling contiguous
    // blocks of memory.
    Block* next;
    char* mem;
};

FixedAllocator::FixedAllocator(int itype_size, int block_size): free_element(0), head(0)
{
    // Initialize the free list.
    type_size = itype_size > sizeof(FreeElement) ? itype_size: sizeof(FreeElement);
    num_block_elements = block_size / type_size;
    if (num_block_elements == 0)
        num_block_elements = 1;
}

FixedAllocator::~FixedAllocator()
{
    // Free each block in the list, popping a block until the stack is empty.
    while (head)
    {
        Block* block = head;
        head = head->next;
        delete[] block->mem;
        delete block;
    }
    free_element = 0;
}

void* FixedAllocator::allocate()
{
    // Common case: just pop free element and return.
    if (free_element)
    {
        void* mem = free_element;
        free_element = free_element->next_element;
        return mem;
    }

    // Rare case when we're out of free elements.
    // Create new block.
    Block* new_block = new Block;
    new_block->mem = new char[type_size * num_block_elements];
    new_block->next = head;
    head = new_block;

    // Push all but one of the new block's elements to the free stack.
    char* mem = new_block->mem;
    for (int j=1; j < num_block_elements; ++j)
    {
        void* ptr = mem + j*type_size;
        FreeElement* element = static_cast<FreeElement*>(ptr);
        element->next_element = free_element;
        free_element = element;
    }
    return mem;
}

void FixedAllocator::deallocate(void* mem)
{
    // Just push a free element to the stack.
    FreeElement* element = static_cast<FreeElement*>(mem);
    element->next_element = free_element;
    free_element = element;
}

```

As for your idea:

> The object pool will use the swap-with-last trick for fast removal (it will invoke the object's ~destructor first)

If you use swap-with-last then you'll end up invalidating pointers to the last object (as well as any indices to it). For a memory allocator, it's similar to creating a data structure except you deal with a very firm requirement that you cannot invalidate pointers to memory that is not freed no matter what. With a free list like the above, you don't have to do that while keeping dirt cheap constant-time allocation and freeing.

Also the free list will give you nice spatial locality for memory chunks you allocate against it if you access the pointers in a sorted sequential fashion. However, if you start freeing and allocating a lot against it and the pointers becoming unsorted, then you could end up with lots of cache misses zig-zagging back and forth in memory. It helps to sort those pointers you get from the allocator periodically if you suffer cache misses (a radix sort can do that really fast). The free list, when combined with sorted pointers, does give you very cache-friendly access patterns, but you do have to keep those pointer reasonably sorted by address.

**With That Said...**

With all that being said, IMO when you feel the need to reach heavily for memory pools or object pools, I consider it a sign that your design is too granular. You'll never be able to find breathing room to optimize *that* much if your designs are very granular.

By granular, I mean like a system where everything in the system depends on a "pixel" object instead of an "image" object, or a "particle" object instead of a "particle emitter" object, or a "dog" object instead of a "dogs" object. To find sufficient breathing room to try all kinds of optimizations like eliminating vptr and virtual dispatch overhead for a boatload of teeny objects, using SoA reps, multithreading the homogeneous processing of many teeny things at a central level without rewriting the entire system, etc., you should be designing things at a coarser level: at the level of a collection of things, or sometimes even a collection of a collection of things.

That applies even for inheritance and OOP-based polymorphism. You don't have to make a `Dog` inherit from a `Mammal`. You can have `Dogs` inheriting from `Mammals` with a `Mammals` interface that contains operations that apply to multiple mammals at once. You can have abstract containers, just like abstract images instead of abstract pixels, and that will leave you so much more breathing room to optimize when you have so many fewer teeny object instances to deal with, and instead a handful of "container object" type instances.

Allocating each and every dog on a heap might be expensive. Allocating a container that could store a million dogs one time on the heap is not so expensive as that overhead is now reduced to 1/1,000,000. The easiest way to reduce the expense of allocating or freeing or accessing or modifying a boatload of teeny objects is to avoid designing a boatload of teeny object types in the first place, and instead design a handful of bigger, coarser types of collection objects.

It's a similar thing for data structures. If you find you need to allocate too often with a linked structure, maybe an unrolled structure would be better, like an unrolled linked list which is not storing one element per node, but many contiguous elements per node:

This is the same idea applied as above. We're amortizing the cost of a linked list by designing a data structure that requires only paying that cost once per entire "collection" of elements, not per element. We're linking collections of elements now, not each and every element individually.

Memory allocators are kinda like reaching under the guts of your data types and structures, and it's always at least a little bit ugly and will never quite get you as far in terms of, say, minimizing memory use and maximizing processing efficiency. I'd consider designing different data types and using different data structures first whenever possible.

If you have to drive an hour just to get a cup of coffee, then the solution isn't necessarily to look for a faster car. It might be a whole lot easier if you just stock up on a month's worth of coffee instead, unless there's like a pretty girl working at the counter that you want to see each time, at which point you might look into a faster car. Design at a coarse level for bulk processing. That's the easiest way to reduce these costs paid on a per-object basis for teeny little objects.

# Answer
> 1 votes
I'd consider "resizing" arrays to be an emergency solution, avoid it as far as possible.

If you truly need dynamic size tables you should build them in two layers. Make a small master table that only contain pointers to fixed size sub tables of the desired table content. When the last sub table is close to full you allocate a new one. You could for instance decide to make a master table of 1024 pointer slots, and have each sub table contain 1024 objects, thus the overhead will never be more than a little over a thousand objects and 1024 pointers, yet you have got room for 1048576 objects while only needing to do simple memory allocations at runtime.

---
Tags: c++, performance, optimization, resource-management
---


# Question
Title: What is moving the camera useful for, if I have to do culling myself?
I'm new to libgdx and especially to using OrthographicCameras. I'm trying to understand how useful they are.

The question is, suppose I have a game map 500 units wide. I have an OrtographicCamera vith a viewport of 50x50. Now If I use SpriteBatch to draw texture of my game map as 500 units (I set projection matrix to cameras combined matrix) and move the camera around as the character moves, is this a right practice to do? If that map is 20000 pixels wide (an entire level for a platformer for example), is this really the way to go? Or should I make my camera and render logic myself (render only part of the map according to current coordinates of the character)? If I need to do this myself, what's moving the camera useful for?

# Answer
First of all, the camera provides the projection for the rendering pipeline. Without a camera you can't define how wide the view is.

Secondly, moving every part of the terrain separately is inconvenient compared to simply moving the camera.
> 0 votes

# Answer
Seems like for your use case , you should definitely use a camera. Not only will it save you the trouble of writing it yourself. The libgdx camera projection matrix is passed to the sprite batch and this "moves" your view.

Just render your map and player: move the player around and have the camera follow the player. Then when you are rendering simple call batch.setProjectionMatrix(yourcams\_projection\_matrix) before you call batch.begin().

Also dont forget that when you use a viewport you should update it whenever your game is rezied via the resize function provided in the Application interface/Adapter.

A last note: when you change your cameras position you must call cam.update() in order for the changes to take effect.
> 0 votes

---
Tags: java, libgdx, viewport
---


# Question
Title: How to make the winner emerge as late as possible in a quiz game?
I have a quiz game with my 4 friends. We've had 3 seasons so far. One season consists of 5 games (every player organizes one). Each game must have a total of 20 points that a player can earn. There are no rules regarding how many questions a game must consist of but the ideal range is 15-25. Season's winner is the player with the most wins. If there's a draw the player who has more points wins.

Sometimes it is quite clear who is going to win the season after the 4th game because he/she has at least 2 wins and leads with around 10 points.

Ideally the winner of the season would emerge after the results of the 5th game are in. Is there any ideas we could implement to make the winner emerge as late as possible and this way make the game more interesting?

# Answer
There are two main strategies you can use here:

**Negative Feedback Loops**

These are "rubber banding" mechanics that give players who are lagging an advantage to help them catch up, or slow the progress for players who are already ahead. This reduces the impact of an early lead, and helps keep players in the running right up to the end. Items in Mario Kart are a good example of this.

In a quiz game this could include things like:

* getting a wrong answer deducts a percentage of the player's score (impacting high-score players more aggressively)
* giving trailing players a bonus question to answer, or a bonus guess if nobody gets the right answer in a round, or a follow-up question based on the previous (more scoring opportunities for players who need a hand)
* if nobody answers a question, one of the players currently in the lead is forced to answer (so an early lead is a liability for penalties)
* a "steal" mechanic that lets a player with a right answer choose who to steal some points from (players will disproportionately pick the leader). You Don't Know Jack's "screw" mechanic that lets players force an opponent to answer functions similarly.

**Escalating Stakes**

The other major strategy is to make later rounds more valuable than early rounds. So while an early lead is good, players who are left behind aren't out of the running - a few wins late in the game can turn the tables, even against an opponent with a strong lead.

You'll often see this done in the form of questions worth progressively more points (see Jeopardy with its player-controlled progression down the columns n the board), a "second half" round of questions that score double, or a final question / minigame like YDKJ's Jack Attack with much higher scoring potential than any previous round.
> 9 votes

---
Tags: game-design
---


# Question
Title: Stop animation after definite time Libgdx
There is a button `TextButton`, there is also an animation s`pinAnimation`. Neither can I understand how to implement the "fading animation" (i.e. when the button is clicked, the animation started, and gradually, after a certain time, stopped). Code Example:

```
@Override
public void create(){

textureAtlas = new TextureAtlas("pack.atlas");
stage = new Stage(new ScreenViewport());
sb = new SpriteBatch();

 final TextButton button = new TextButton("Start",skin , "default");
        button.setWidth(220);
        button.setHeight(50);

  button.addListener(new ClickListener(){
            @Override
            public void clicked(InputEvent event, float x, float y) {
                spinAnimation.setFrameDuration(0.5f);
                int i = 0;

            }
        });

    stage.addActor(button);

           Gdx.input.setInputProcessor(stage);
    }

@Override
   public void render() {

   elepsedTime += Gdx.graphics.getDeltaTime();
   Gdx.gl.glClearColor(0,0,0,1);
   Gdx.gl.glClear(com.badlogic.gdx.graphics.GL20.GL_COLOR_BUFFER_BIT);

   sb.begin();
   stage.act(Gdx.graphics.getDeltaTime());
   sb.draw(spinAnimation.getKeyFrame(elepsedTime,true), 50,  60

   sb.end();
   stage.draw();
    }

```

# Answer
> 0 votes
Keep a duration variable for as long as you want the animation to keep going. Also have another variable that checks if your animation has started. in your click listener switch `started = true`, and in your render loop do something like :

```
if(started){
    elapsed+=delta;
    if(elapsed < duration){
     //draw your animation
    }
}

```

---
Tags: java, libgdx
---


# Question
Title: Dynamic Memory Allocation and Memory Management
In an average game, there are hundreds or maybe thousands of objects in the scene. Is it completely correct to allocate memory for all objects, including gun shots (bullets), **dynamically via default *new()*?**

Should I create any **memory pool for dynamic allocation**, or is there no need to bother with this? What if the target platform are mobile devices?

Is there a need for a **memory manager** in a mobile game, please? Thank you.

*Language Used: C++; Currently developed under Windows, but planned to be ported later.*

# Answer
> In an average game, there are hundreds or maybe thousands of obects in the scene. Is it completely correct to allocate memory for all objects, includiding gun shots(bullets), dynamically via default new()?

That really depends what you mean by "correct." If you take the term quite literally (and ignore any concept of correctness of the implied design) then yes, it is perfectly acceptable. Your program will compile and run fine.

It may perform sub-optimally, but it still may also perform well enough to be a shippable, fun game.

> Should I create any memory pool for dynamic allocation, or is there no need to bother with this? What if the target platform are mobile devices?

Profile and see. In C++, for example, dynamically allocation on the heap is usually a "slow" operation (in that it involves walking through the heap looking for a block of appropriate size). In C#, it's usually an extremely fast operation because it involves little more than an increment. Different language implementations have different performance characteristics with respect to memory allocation, fragmentation upon release, et cetera.

Implementing a memory pooling system can certainly bring about performance gains -- and since mobile systems are usually underpowered relative to desktop systems, you may see more of a gain on a particular mobile platform than you would on a desktop. But again, you'd have to profile and see -- if, currently, your game is slow but memory allocation/release doesn't show up on the profiler as a hot spot, implementing infrastructure to optimize memory allocation and access probably won't get you much bang for your buck.

> Is there a need for a memory manager in a mobile game, please? Thank you.

Again, profile and see. Is your game running fine now? Then you may not need to worry.

All of that cautionary-speak aside, using dynamic allocation for everything isn't strictly speaking *necessary* and so it can be advantageous to avoid it -- both because of the potential performance gains, and because allocating memory that you need to track and eventually release means you have to track and eventually release it, possibly complicating your code.

In particular, in your original example you cited "bullets," which tend to be something that get created and destroyed frequently -- because many games involve lots of bullets, and bullets move fast and thus reach the end of their lifetime quickly (and often violently!). So implementing a pool allocator for them and objects like them (such as particles in a particle system) can usually result in efficiency gains and would likely be the first place to start looking at using pool allocation.

I am unclear if you are considering a memory pool implementation to be distinct from a "memory manager" -- a memory pool is a relatively well-defined concept, so I can say with some certainty that they can be a benefit if you implement them. A "memory manager" is a bit more vague in terms of its responsibility, so I would have to say that whether or not one is required depends on what you think that "memory manager" would do.

For example if you consider a memory manager to be a thing that just intercepts calls to new/delete/free/malloc/whatever and provides diagnostics on how much memory you allocate, what you leak, et cetera -- then that can be a useful tool for the game while it's in development to help you debug leaks and tune your optimal memory pool sizes, and so on.
> 23 votes

# Answer
I don't have much to add to Josh's excellent answer, but I'll comment on this:

> Should I create any memory pool for dynamic allocation, or is there no need to bother with this?

There is a middle ground between memory pools and calling `new` on each allocation. For example, you can allocate a set number of objects in an array, then set a flag on them to 'destroy' them later. When you need to allocate more, you can overwrite the ones with the destroyed flag set. This kind of thing is only slightly more complex to use than new/delete (as you would have 2 new functions for that purpose) but is simple to write and can give you big gains.
> 7 votes

# Answer
> Is it completely correct to allocate memory for all objects, including gun shots (bullets), dynamically via default new()?

No, of course not. No memory allocation is correct for *all* objects. operator new() is for *dynamic* allocation, that is, it is appropriate only if you need the allocation to be dynamic, either because the object's lifetime is dynamic or because the type of the object is dynamic. If the type and lifetime of the object are known statically, you should allocate it statically.

Of course, the more information you have about your allocation patterns, the faster these allocations can be made via specialist allocators, such as object pools. But, these are optimizations and you should only make them if they're known to be necessary.
> 3 votes

# Answer
Kind of echoing Kylotan's suggestion but I would recommend solving this at the data structure level when possible, not at the lower allocator level if you can help it.

Here's a simple example of how you can avoid allocating and freeing `Foos` repeatedly using an array with holes with elements linked together (solving this at a "container" level instead of an "allocator" level):

```
struct FooNode
{
    explicit FooNode(const Foo& ielement): element(ielement), next(-1) {}

    // Stores a 'Foo'.
    Foo element;

    // Points to the next foo available; either the
    // next used foo or the next deleted foo. Can
    // use SoA and hoist this out if Foo doesn't
    // have 32-bit alignment.
    int next;
};

struct Foos
{
    // Stores all the Foo nodes.
    vector<FooNode> nodes;

    // Points to the first used node.
    int first_node;

    // Points to the first free node.
    int free_node;

    Foos(): first_node(-1), free_node(-1)
    {
    }

    const FooNode& operator[](int n) const
    {
         return data[n];
    }

    void insert(const Foo& element)
    {
         int index = free_node;
         if (index != -1)
         {
              // If there's a free node available,
              // pop it from the free list, overwrite it,
              // and push it to the used list.
              free_node = data[index].next;
              data[index].next = first_node;
              data[index].element = element;
              first_node = index;
         }
         else
         {
              // If there's no free node available, add a
              // new node and push it to the used list.
              FooNode new_node(element);
              new_node.next = first_node;
              first_node = data.size() - 1;
              data.push_back(new_node);
         }
    }

    void erase(int n)
    {
         // If the node being removed is the first used
         // node, pop it from the used list.
         if (first_node == n)
              first_node = data[n].next;

         // Push the node to the free list.
         data[n].next = free_node;
         free_node = n;
    }
};

```

Something to this effect: a singly-linked index list with a free list. The index links allow you to skip over removed elements, remove elements in constant-time, and also reclaim/reuse/overwrite free elements with constant-time insertion. To iterate through the structure, you do something like this:

```
for (int index = foos.first_node; index != -1; index = foos[index].next)
    // do something with foos[index]

```

And you can generalize the above kind of "linked array of holes" data structure using templates, placement new and manual dtor invocation to avoid the requirement for copy assignment, make it invoke destructors when elements are removed, provide a forward iterator, etc. I chose to keep the example very C-like to more clearly illustrate the concept and also because I'm very lazy.

That said, this structure does tend to degrade in spatial locality after you remove and insert things a lot to/from the middle. At that point the `next` links could have you walking back and forth along the vector, reloading data formerly evicted from a cache line within the same sequential traversal (this is inevitable with any data structure or allocator that allows constant-time removal without shuffling elements while reclaiming spaces from the middle with constant-time insertion and without using something like a parallel bitset or a `removed` flag). To restore the cache-friendliness, you can implement a copy ctor and swap method like this:

```
Foos(const Foos& other)
{
    for (int index = other.first_node; index != -1; index = other[index].next)
        insert(foos[index].element);
}

void Foos::swap(Foos& other)
{
     nodes.swap(other.nodes):
     std::swap(first_node, other.first_node);
     std::swap(free_node, other.free_node);
}

// ... then just copy and swap:
Foos(foos).swap(foos);

```

Now the new version is cache-friendly again to traverse. Another method is store a separate list of indices into the structure and sort them periodically. Another is to use a bitset to indicate what indices are used. That will always have you traversing the bitset in sequential order (to do this efficiently, check 64-bits at a time e.g. using FFS/FFZ). The bitset is the most efficient and non-intrusive, requiring only a parallel bit per element to indicate which ones are used and which are removed instead of requiring 32-bit `next` indices, but the most time-consuming to write well (it won't be fast for traversal if you're checking one bit at a time -- you need FFS/FFZ to find a set or unset bit immediately among 32+ bits at a time to rapidly determine ranges of occupied indices).

This linked solution is generally the easiest to implement and non-intrusive (doesn't require modifying `Foo` to store some `removed` flag) which is helpful if you want to generalize this container to work with any data type if you don't mind that 32-bit overhead per element.

> Should I create any memory pool for dynamic allocation, or is there no need to bother with this? What if the target platform are mobile devices?

*need* is a strong word and I'm biased working in very performance-critical areas like raytracing, image processing, particle simulations, and mesh processing, but it is relatively very expensive to be allocating and freeing teeny objects used for very light processing like bullets and particles individually against a general-purpose, variable-sized memory allocator. Given that you should be able to generalize the above data structure in a day or two to store anything you want, I think it'd be a worthwhile exchange to eliminate such heap allocation/deallocation costs outright from being paid for every single teeny thing. On top of reducing allocation/deallocation costs, you get better locality of reference traversing the results (fewer cache misses and page faults, i.e.).

As for what Josh mentioned about GC, I haven't studied C#'s GC implementation quite as closely as Java's, but GC allocators often have an *initial allocation* that's very fast because that's using a sequential allocator which can't free memory from the middle (almost like a stack, you can't delete things form the middle). Then it pays for the expensive costs to actually allow removing individual objects in a separate thread by copying memory and purging the formerly allocated memory as a whole (like destroying the entire stack at once while copying the data to something more like a linked structure), but because it's done in a separate thread, it doesn't necessarily stall your application's threads so much. However, that carries a very significant hidden cost of an additional level of indirection and the general loss of LOR after an initial GC cycle. It is another strategy to speeding up allocation though -- make it cheaper in the calling thread and then do the expensive work in another. For that you need two levels of indirection to reference your objects instead of one since they will end up getting shuffled in memory between the time you initially allocate and after a first cycle.

Another strategy in a similar vein that's a little easier to apply in C++ is just don't bother to free your objects in your main threads. Just keeping adding and adding and adding to the end of a data structure which doesn't allow removing things from the middle. However, mark those things that need to be removed. Then a separate thread could take care of the expensive work of creating a new data structure without the removed elements and then atomically swap the new one with the old one, e.g. Much of the cost of both allocating and freeing elements can be passed on to a separate thread if you can make the assumption that requesting to remove an element doesn't have to be satisfied immediately. That not only makes freeing cheaper as far as your threads are concerned but makes allocation cheaper, since you can use a much simpler and dumber data structure which never has to handle removal cases from the middle. It's like a container that only needs a `push_back` function for insertion, a `clear` function to remove all elements, and `swap` to swap contents with a new, compact container excluding removed elements; that's it as far as mutating goes.
> 0 votes

---
Tags: architecture, mobile, memory-efficiency
---


# Question
Title: Libgdx stop animation at last animated frame
How i can stop animation at last frame.

```
@Override
public void create(){

textureAtlas = new TextureAtlas("pack.atlas");
stage = new Stage(new ScreenViewport());
sb = new SpriteBatch();

 final TextButton button = new TextButton("Start",skin , "default");
        button.setWidth(220);
        button.setHeight(50);

  button.addListener(new ClickListener(){
            @Override
            public void clicked(InputEvent event, float x, float y) {
                spinAnimation.setFrameDuration(0.5f);
                int i = 0;
     Timer.schedule(new Timer.Task() {
                @Override
                public void run() {
                    spinAnimation.setFrameDuration(0f);

                }

            },1);

            }
        });

    stage.addActor(button);

           Gdx.input.setInputProcessor(stage);
    }

@Override
   public void render() {

   elepsedTime += Gdx.graphics.getDeltaTime();
   Gdx.gl.glClearColor(0,0,0,1);
   Gdx.gl.glClear(com.badlogic.gdx.graphics.GL20.GL_COLOR_BUFFER_BIT);

   sb.begin();
   stage.act(Gdx.graphics.getDeltaTime());
   sb.draw(spinAnimation.getKeyFrame(elepsedTime,true), 50,  60

   sb.end();
   stage.draw();
    }

```

# Answer
> 1 votes
do `spinAnimation.getKeyFrame(Math.min(elapsedTime,spinAnimation.getAnimationDuration()),true)`

or you know just dont have the animation looping. `spinAnimation.getKeyFrame(elapsedTime,false)`

and make sure `PlayMode` is set to `PlayMode.NORMAL`. If you didnt change it before then it should already be set to normal.

---
Tags: java, libgdx, animation
---


# Question
Title: How can I render attack ranges as in this screenshot?
*Divinity: Original Sin 2* has an amazing range-of-attack display. When I select a character's abilities, the range of the ability will appear (as shown in the screenshot below).

I'd like to know how to create an effect like this.

You can see this system in motion via this YouTube video

---

I think It just displayed navmesh , so I tried to display my navmesh.I used `NavMesh.CalculateTriangulation()` , `GL API` to displaying.

After baking navmesh attach this script to your camera and give this a material:

```
using System.Collections;
using System.Collections.Generic;
using UnityEngine.AI;
using UnityEngine;

public class NavmeshDebuger: MonoBehaviour {
    public Material material;

    void OnPostRender() {
        var triangulation = NavMesh.CalculateTriangulation();
        if (material == null) {
            return;
        }
        GL.PushMatrix();

        material.SetPass(0);
        GL.Begin(GL.TRIANGLES);
        for (int i = 0; i < triangulation.indices.Length; i += 3) {
            var triangleIndex = i / 3;
            var i1 = triangulation.indices[i];
            var i2 = triangulation.indices[i + 1];
            var i3 = triangulation.indices[i + 2];
            var p1 = triangulation.vertices[i1];
            var p2 = triangulation.vertices[i2];
            var p3 = triangulation.vertices[i3];
            var areaIndex = triangulation.areas[triangleIndex];
            Color color;
            switch (areaIndex) {
            case 0:
                color = Color.red; break;
            case 1:
                color = Color.green; break;
            default:
                color = Color.blue; break;
            }
            GL.Color(color);
            GL.Vertex(p1);
            GL.Vertex(p2);
            GL.Vertex(p3);
        }
        GL.End();

        GL.PopMatrix();
    }

}

```

# Answer
> 1 votes
I believe you want to extrude the mesh at each vertex by moving it out by the normal * some fixed scalar. (This leads to some issues around edges)

Here is a more detailed explanation: How do I generate a 3D race track from a spline?

and https://stackoverflow.com/questions/3039026/edges-on-polygon-outlines-not-always-correct/3058978#3058978 for corners

---
Tags: unity, c#
---


# Question
Title: How to limit where an object spawns GameMaker Studio 2
When the game starts, I am trying to generate an object in a random area. It's working, but sometimes the object spawns in the players view.

How to have an object that generates in a random location, but not in the player's view?

# Answer
You can use the function `rectangle_in_rectangle` to check if the bounding box of the object is inside the bounding box of the camera.

```
place_object_at_random_position()
var cameraLeft = bview_xview[0]
var cameraTop = view_yview[0]
var cameraRight = view_xview[0] + view_wview[0]
var cameraBottom = view_yview[0] + view_hview[0]
while (rectangle_in_rectangle(bbox_left, bbox_top, bbox_right, bbox_bottom,
                              cameraLeft, cameraTop, cameraRight, cameraBottom)) {
    place_object_at_random_position()
}

```

If you for some reason cannot access the object's bounding box (`bbox_left` etc.) you can use `point_in_rectangle` instead.

```
var x = random_range(min, max)
var y = random_range(min, max)
var cameraLeft = bview_xview[0]
var cameraTop = view_yview[0]
var cameraRight = view_xview[0] + view_wview[0]
var cameraBottom = view_yview[0] + view_hview[0]
while (point_in_rectangle(x, y, cameraLeft, cameraTop, cameraRight, cameraBottom)) {
    x = random_range(min, max)
    y = random_range(min, max)
}

create_object_at(x, y)

```

The functions `place_object_at_random_position` and `create_object_at` are functions you define yourself.
> 0 votes

---
Tags: game-maker, spawning
---


# Question
Title: Manually creating an instance of object derived from MonoBehaviour
I'm currently "newing" an instance of a class I have that derives from MonoBehaviour and store it in a list. The value of this instance is "null" however, even though it has all the fields of my derived class in it so it passes as null in null checks. After more reading it seems it's a bad idea to manually new up an instance of an object that derives from MonoBehaviour.

The class is an Actor class. I have a situation where enemy actors are 3D models in my scene and so I want them to derive from MonoBehaviour, but the player actors don't have world representations really. I just have a picture of them in the corner. Similar to Legend of Grimrock.

I wanted the 1 Actor class since the data they need is all the same and I wanted to avoid having 2 classes for no seemingly reason other than not newing up a MonoBehaviour derived class.

What are my options with this requirement when my player actors don't need MonoBehaviour but my enemy actors do but they all need to have the same properties?

# Answer
You should be seeing a warning in the compiler log about newing a MonoBehavior directly. Always pay attention to the log.

MonoBehavior classes are really components and wont function without being attached to a GameObject instance.

```
GameObject object = new GameObject();
MyMonoBehavior mine = object.AddComponent<MyMonoBehavior>();
mine.specialValue = 42;

```

While it's difficult to be sure if this next part is relevant without seeing code samples, not everything has to be a MonoBehavior. MonoBehaviors give you a hook directly into the game loop. If what you have is meant to be data-only, and you don't need it to do calculations every frame, you can create normal classes and use them in other MonoBehaviors.
> 1 votes

---
Tags: unity
---


# Question
Title: Alternative to 2D array in a tiled-map structure
After searching for a long time, I'm surprised this question was not asked yet. In a 2D, tiled-map game, how do you handle the map ? I'd be glad to have your point of view in any languages, though I'm more interested in C++ implementations.

A 2D array, a 2D vector, a class handling a linked-list with ad hoc computing to handle coordinates, a boost::matrix... ? What solution do you use and why ?

# Answer
One thing I've done for an RPG style map - that is, houses you can enter, dungeons, etc is have 4 main structures: a Map, an Area, a Zone, and a Tile.

A Tile is obviously a tile.
A Zone, or a chunk, or whatever, is an area of X by Y tiles. This has a 2D array.
An Area is a collection of Zones. Each Area can have different Zone sizes - the overworld may use a 32x32 Zone, whereas a house may have one 10x20 Zone. These are stored in dictionaries (so I can have Zone (-3, -2)).
A Map is a collection of Areas, all of which are linked to each other.

I felt this allowed me greater flexibility rather than having one huge map.
> 10 votes

# Answer
I'll explain what I do for a specific case of tiled maps: this is for effectively infinite maps, ones where the world is generated on demand but you need to save modifications to it:

I define some cell size "N" and split the world up into squares/cubes "NxN" or "NxNxN"

A cell will have a unique key. I generate mine by hashing or using directly the formatted string:"%i,%i,%i",x,y,z (where x,y,z are the world coordinates of the start of the cell divided by N)

Storing the tiles indices in arrays is straightforward as you know you have NxN tiles or NxNxN tiles. You also know how many bits your tile type takes up. Just use a linear array. It makes loading and saving/releasing the cells simpler to handle too.

Any accessor merely needs to generate the key for the cell (to make sure it's loaded/generated, then get the pointer to it), then use a sub index to look inside that cell. to find the tile value at that specific point.

Extracting the cell by its key, I currently use a map/dictionary as generally I process whole cells at once (wouldn't want to know how bad a hit it would be to do a dictionary lookup per tile, eek).

Another point, I don't keep mobs / players in the cell data. The actively dynamic stuff needs its own system.
> 5 votes

# Answer
The question probably wasn't asked because you don't need an alternative. For me, it's:

`Tile tiles[MAP_HEIGHT][MAP_WIDTH];` if the size is fixed.

`std::vector<Tile> tiles(MAP_HEIGHT*MAP_WIDTH);` otherwise.
> 5 votes

# Answer
It would depend on the style of game and map honestly. For a relatively small rectangular tile map, I'd probably just stick with a 2d array. If the map was very irregularly shaped (lots of empty gaps), a wrapper around linked lists that provides O(1) indexing would probably be my choice.

An integer indexed array gives you a 2147483647^2 2d array. That's pretty big, but exceeds what you'd what to load into memory. If the map was to be large scale, another thing to look at is dividing the map into chunks. Each chunk is fixed size and contains a sub-array of tiles that could be loaded/unloaded as needed to keep memory lower.
> 2 votes

# Answer
If it's just a simple tiled game on a grid like a turn-based strategy game, then something like this:

```
struct Tile
{
    // Stores the first entity (enemy, NPC, item, etc) on the tile.
    int first_entity;
    ...
};

struct Entity
{
    // Stores the next entity on the same tile or
    // the next free entity index to reclaim if
    // this entity has been freed/removed.
    int next;
    ...
};

struct Row
{
    // Stores all the tiles on the row.
    vector<Tile> tiles;

    // Stores all the entities on the row.
    vector<Entity> entities;

    // Points to the first free entity index
    // to reclaim on insertion.
    int first_free;
};

struct Map
{
    // Stores all the rows in the map.
    vector<Row> rows;
};

```

Some people might wonder why I choose to store separate vectors for each map row. It's to improve spatial locality as we traverse the entities standing on a given tile. When we store a separate vector per row, then all the entities for that row might fit in L1 or L2, whereas they might not even fit in L3 if we stored one entity container for all entities in the entire map. That still tends to be quite cheap compared to, say, storing a separate vector per tile.

To get, say, the tile at `(102, 72)`, we do this:

```
Row& row = map.rows[72];
Tile& tile = row.tiles[102];

```

To traverse the entities on the tile we do:

```
int entity = tile.first_entity;
while (entity != -1)
{
    // Do something with the entity on the tile.
    ...

    // Advance to the next entity on the tile.
    entity = row.entities[entity].next;
}

```

Naturally for "separate container per row" type implementation to benefit most, your tile access patterns should try to process all the columns of interest for a row before you move to the next, not so much zig-zagging back and forth from one row to the next and back again.

Insertion of an entity to a tile would be like this:

```
int Map::insert_entity(Entity ent, int col_idx, int row_idx)
{
     Row& row = rows[row_idx];

     int ent_idx = row.first_free;
     if (ent_idx != -1)
     {
          row.first_free = row.entities[ent_idx].next;
          row.entities[ent_idx] = ent;
     }
     else
     {
          ent_idx = static_cast<int>(row.entities.size());
          row.entities.push_back(ent);
     }

     Tile& tile = row.tiles[col_idx];
     row.entities[ent_idx].next = tile.first_entity;
     tile.first_entity = ent_idx;
     return ent_idx;
}

```

... and removal:

```
void Map::remove_entity(int ent_idx, int col_idx, int row_idx)
{
     Row& row = rows[row_idx];
     Tile& tile = row.tiles[col_idx];
     if (tile.first_entity = ent_idx)
         tile.first_entity = row.entities[ent_idx].next;

     row.entities[ent_idx].next = row.first_free;
     row.first_free = ent_idx;
}

```

Main reason I like this solution is that we avoid storing too many vectors (ex: one vector per tile: too many for big maps), but not so few that iterating through the entities on a given tile leads to epic strides across the memory address space and lotsa cache misses. One entity vector per row strikes a nice balance there.

This is assuming that you have things like buildings and enemies and items and treasure chests and players standing on the tiles and that a lot of the time spent in the game logic is accessing the entities standing on those tiles as well as checking what entities are on a given tile. Otherwise I'd use a 1D array approach with a single vector for all tiles as that would be the most efficient for just accessing tiles. You can then get a tile using: `tiles[row*num_cols+col]` Use a one-dimensional array if in doubt since it will let you traverse things in a straightforward sequential order without nested loops and only require one heap allocation to allocate the entire thing.

Just in general the separate dynamic array per row is something I've found to reduce cache misses a lot in cases in cases where your grid is storing elements inside of it. Of course if it doesn't and your grid is just like an image containing pixels, then it makes no sense to use a separate dynamic array per row. As a recent benchmark where I optimized something grid-like this way (before it was just using one giant array for everything; I optimized it to store a separate dynamic array per row after seeing lots of cache misses in vtune):

Before:

```
--------------------------------------------
- test_grid
--------------------------------------------
time passed for 'insert': {1.799000 secs}
mem use after 'insert': 479,508,224 bytes

8560 cells, 1000000 rects
finished test_grid: {1.919000 secs}

```

After:

```
--------------------------------------------
- test_grid
--------------------------------------------
time passed for 'insert': {0.310000 secs}
mem use after 'insert': 410,546,720 bytes

8560 cells, 1000000 rects
finished test_grid: {0.361000 secs}

```

And I used the same kind of strategy described above. As a bonus you can also see it reduced memory usage because the vectors storing the entities tend to make a tighter fit if you store one per row instead of one for the entire map.

Note that the above test to insert a million entities to the grid might seem like it's taking a long time and lotsa memory even after the optimization. That's because each entity I'm inserting takes many tiles, averaging about 100 tiles per entity (10x10 average size). So I'm inserting each of the million entities to an average of 100 grid tiles which makes it more like inserting 100 million entities than a measly 1 million entities. It's stress testing a pathological case. If I'm just inserting a million entities that occupy 1 tile each, I can do it in milliseconds and just using about 16 megabytes of memory.

In my case I often even have to make pathological cases efficient since I work in VFX instead of gaming. I can't tell artists, *"Make your content this way for this engine,"* since the whole point of VFX is to let the artists create the content however they want. They then optimize it before they export to their favorite engine, but I have to deal with the unoptimized stuff which means I do often have to efficiently handle the pathological cases, like an octree having to efficiently deal with massive triangles that span the entire scene since the artists create such content and frequently (far more often than one might expect). So anyway, that above test is testing something that should never happen and that's why it takes almost a third of a second to insert a million entities, but in my case those "should never happen" things happen all the time. So the pathological case isn't a rare case for me, though the row-based optimization described above equally optimizes both the common-common case and the common-pathological case.

As a side bonus, this also allows you to insert and remove entities for multiple rows simultaneously in parallel using multithreading without locking, since you can now safely do it given that each row has a separate entity container provided that two threads aren't trying to insert/remove stuff to/from the same row simultaneously.
> 2 votes

# Answer
I am toying with a 3D engine where the world is a mesh.

I am importing some 2D maps+tilesets that have previously been made.

And when I do, I convert it to a 3D mesh and put all the tiles into a single texture.

This draws substantially faster.

I would perhaps keep the map around in a 1D array of w\*h if I had to keep it's tile concept, but my answer is that its liberating to move beyond the 2Dness.

And, if you have performance problems whilst using GPU drawing, keeping the graphical representation as a single texture - with a mesh if its got variable heights - can really speed it up compared to drawing each tile individually.
> 0 votes

---
Tags: c++, tiles, data-structure, maps
---


# Question
Title: Quad tree vs Grid based collision detection
I'm making a 4 player co-op r-type game, and I'm about to implement the collision detection code. I've read a lot of articles and stuff about how to handle collision detection, but I'm having a hard time figuring out what to go with. It seems the quad tree is the most common way to go, but in some resources they mention the grid based solution. For having used a grid for detections in a previous game, I'm comfortable with that, but is it actually better than a quad tree ? I'm not sure which offers best performance, and I've also ran a little benchmark, there is not much difference between both solutions.

Is one better than the other ? or more elegant ? I'm really not sure which one I should use.

Any advice is welcome. Thanks.

# Answer
> 36 votes
The right answer depends a little bit on the actual game you're designing, and choosing one over the other is really going to require implementing both and doing profiling to find out which one is more time or space efficient on your specific game.

Grid detection seems to only apply to detecting collisions between moving objects and a static background. The biggest advantage to this is that the static background is represented as a contiguous memory array, and each collision lookup is O(1) with good locality if you need to do multiple reads (because entities cover more than one cell in the grid). The disadvantage, if the static background is large, is that the grid can be rather wasteful of space.

If instead you represent the static background as quadtree, then the cost of individual lookups goes up, but because large blocks of the background take up a small amount of space, the memory requirements go down, and so more of the background can sit in the cache. even if it takes 10 times as many reads to do a lookup in such a structure, if it's all in the cache, it'll still be 10 times faster than a single lookup with a cache miss.

If I were faced with the choice? I'd go with the grid implementation, because it's stupid simple to do, better spend my time on other, more interesting problems. If I notice that my game is running a little slow, I'll do some profiling and see what could use some help. If it looks like the game is spending a lot of time doing collision detection, I'd try another implementation, like a quadtree (after exhausting all easy fixes first), and find out if that helped.

**Edit:** I haven't got a clue how grid collision detection relates to detecting collisions of multiple, mobile entities, but instead, i'll answer how a spatial index (Quadtree) improves detection performance over the iterative solution. The naive (and typically perfectly fine) solution looks sort of like this:

```
foreach actor in actorList:
    foreach target in actorList:
        if (actor != target) and actor.boundingbox intersects target.boundingbox:
            actor.doCollision(target)

```

This obviously has performance around O(n^2), with n the number of actors that are currently alive in the game, including bullets and spaceships and aliens. It can also include small static obstacles.

This works fantastically well so long as the number of such items is reasonably small, but starts to look a little poor when there's more than a few hundred objects to check against. 10 objects results in just 100 collision checks, 100 results in 10,000 checks. 1000 results in one million checks.

A spatial index (like quadtrees) can efficiently enumerate the items it collects according to geometric relationships. this would change the collision algorithm to something like this:

```
foreach actor in actorList:
    foreach target in actorIndex.neighbors(actor.boundingbox):
       if (actor != target) and actor.boundingbox intersects target.boundingbox:
            actor.doCollision(target)

```

The efficiency of this (assuming a uniform distribution of entities): is usually O(n^1.5 log(n)), since the index takes about log(n) comparisons to traverse, there will be about sqrt(n) neighbors to compare, and there are n actors to check. Realistically, though, the number of neighbors is always quite limited, since if a collision does occur, most of the time one of the objects is deleted, or moved away from the collision. thus you get just O(n log(n)). For 10 entities, you do (about) 10 comparisons, for 100, you do 200, for 1000 you do 3000.

A really clever index can even combine the neighbor search with the bulk iteration, and perform a callback on each intersecting entity. This will give a performance of about O(n), since the index is being scanned once rather than queried n times.

# Answer
> 7 votes
Sorry for resurrecting ancient thread but IMHO plain old grids aren't used often enough for these cases. There's lot of advantages to a grid in that cell insertion/removal is dirt cheap. You don't have to bother with freeing a cell since the grid has no aim to optimize for sparse representations. I say that having reduced the time to marquee select a bunch of elements in a legacy codebase from over 1200ms down to 20ms by just replacing the quad-tree with a grid. In fairness though, that quad-tree was really poorly implemented, storing a separate dynamic array per leaf node for the elements.

The other one that I find *extremely* useful is that your classic rasterization algorithms for drawing shapes can be used to do searches into the grid. For example, you can use Bresenham line rasterization to search for elements that intersect a line, scanline rasterization to find what cells intersect a polygon, etc. Since I work a lot in image processing, it's really nice to be able to use the exact same optimized code I use to plot pixels to an image as I use to detect intersections against moving objects in a grid.

That said, to make a grid efficient, you shouldn't need more than 32-bits per grid cell. You should be able to store a million cells in under 4 megabytes. Each grid cell can just index the first element in the cell, and the first element in the cell can then index the next element in the cell. If you're storing some kind of full-blown container with every single cell, that gets explosive in memory use and allocations quickly. Instead you can just do:

```
struct Node
{
    int32_t next;
    ...
};

struct Grid
{
     vector<int32_t> cells;
     vector<Node> nodes;
};

```

Like so:

Okay, so on to the cons. I'm coming at this admittedly with a bias and preference towards grids, but their main disadvantage is that they aren't sparse.

Accessing a specific grid cell given a coordinate is constant-time and doesn't require descending down a tree which is cheaper, but the grid is dense, not sparse, so you could end up having to check more cells than required. In situations where your data is very sparsely distributed, the grid could require checking way more to figure out the elements that intersect say a line or a filled polygon or a rectangle or a bounding circle. The grid has to store that 32-bit cell even if it's completely vacant, and when you're doing a shape intersection query, you have to check those empty cells if they intersect your shape.

The quad-tree's main benefit is naturally its ability to store sparse data and only subdivide as much as needed. That said, it's harder to implement really well, especially if you have things moving around every frame. The tree needs to subdivide and free child nodes on the fly very efficiently, otherwise it degrades into a dense grid wasting overhead to store parent-\>child links. It's very doable to implement an efficient quad-tree using very similar techniques to what I described above for the grid, but generally going to be more time-intensive. And if you do it the way I do in the grid, that's not necessarily optimal either, since it would lead to a loss in the ability to guarantee that all 4 children of a quad-tree node are stored contiguously.

Also both a quad-tree and grid don't do a magnificent job if you have a number of large elements that span much of the entire scene, but at least the grid stays flat and doesn't subdivide to the nth degree in those cases. The quad-tree should store elements in branches and not just leaves to reasonably handle such cases or else it will want to subdivide like crazy and degrade in quality extremely rapidly. There are more pathological cases like this you have to take care of with a quad-tree if you want it to handle the widest range of content. For example, another case that can really trip up a quad-tree is if you have a boatload of coincident elements. At that point some people just resort to setting a depth limit for their quad-tree to prevent it from subdividing infinitely. The grid has an appeal that it does a decent job, kind of a jack-of-all-trades, against a wide range of inputs, and it takes a very steady and predictable amount of memory no matter what you do (32-bit overhead per cell, 32-bit overhead per element inserted in cell).

The stability and predictability is also beneficial in a game context, since sometimes you don't necessarily want the fastest solution possible for the common case if it could occasionally lead to hiccups in frame rates in rare case scenarios versus a solution that's reasonably fast all-around but never leads to such hiccups and keeps frame rates smooth and predictable. A grid has that kind of latter quality going for it.

With all that said, I really think it's up to the programmer. With things like grid vs. quad-tree or octree vs. kd-tree vs. BVH, my vote is on the most prolific developer with a record for creating very efficient solutions no matter what data structure he/she uses. There's a whole lot at the micro-level too, like multithreading, SIMD, cache-friendly memory layouts and access patterns. Some people might consider those micro but they don't necessarily have a micro impact. Such things could make a 100x difference from one solution to the other. In spite of this, if I was personally given a few days and was told I need to implement a data structure to rapidly accelerate collision detection of elements moving around every frame, I'd do better in that short time implementing a grid than a quad-tree. My probability of making a mistake would be significantly lower, my probability of ending up with a more efficient well-rounded solution in that time would be higher, I would have more time to seek micro-optimizations like SIMD, multithreading, etc, I'd be able to write a more thorough unit test potentially, create more documentation, and so forth.

---
Tags: c++, algorithm, collision-detection, physics
---


# Question
Title: Global fog does not work with deferred rendering in Unity
When I set deferred rendering the global fog from the Unity Standard Assets does not work, there is no fog at all. With forward rendering the global fog works. How do I add fog with deferred rendering?

# Answer
Download this: https://www.assetstore.unity3d.com/en/#!/content/83912

After Downloading it attach the "Post Processing Behaviour" Script to your Main Camera. The Script comes with the Package. Right-Click into your assets folder and create a new "Post-Processing Profile". Drag that into the empty Slow in the Inspector in the newly added Script on your Main Camera. Select the Post-Processing Profile and in the Inspector Check "Fog".
> 0 votes

---
Tags: unity, deferred-rendering, fog
---


# Question
Title: Throwing Exceptions in C++ game DLL's? Pros and Cons
What are the **pros** and **cons** of using Exceptions in C++ in relation to game development.

Google style guide says that they don't use Exceptions for a variety of reasons. Are the same reasons pertinent towards game development?

> We do not use C++ exceptions... *\- google-styleguide.googlecode.com*

Some issues to think about.

* How it pertains to the development of a libraries used through multiple projects.
* How does it affect unit testing, integration testing, etc?
* What does it do to using third party libraries.

# Answer
There are also some nasty consequences for using exceptions in C++ if you don't know all the details of how they work. Since many games are written in C++ this may be a factor.

For example, in C++ throwing an exception in a destructor can have serious consequences. It can cause all kinds of undefined behavior and crashes, because you can get trapped in a situation where you have more than one active exception in flight. (See Item #8 of Effective C++ for more info on this.)
> 7 votes

# Answer
Joel on Software's views of Exceptions.

Interesting view not currently in any of the answers,

> The reasoning is that I consider exceptions to be no better than "goto's", considered harmful since the 1960s, in that they create an abrupt jump from one point of code to another. In fact they are significantly worse than goto's:
>
> 1. **They are invisible in the source code.** Looking at a block of code, including functions which may or may not throw exceptions, there is no way to see which exceptions might be thrown and from where. This means that even careful code inspection doesn't reveal potential bugs.
> 2. **They create too many possible exit points for a function.** To write correct code, you really have to think about every possible code path through your function. Every time you call a function that can raise an exception and don't catch it on the spot, you create opportunities for surprise bugs caused by functions that terminated abruptly, leaving data in an inconsistent state, or other code paths that you didn't think about.

http://www.joelonsoftware.com/items/2003/10/13.html
> 9 votes

# Answer
Exceptions are not supported and therefore highly discouraged in at least one modern console development environment.

Most console developers I know prefer not to use them anyway due to added overhead in the executable and the philosophy that they're just plain not needed. RTTI is viewed the same way.
> 5 votes

# Answer
Of all the projects I worked on in games, none of them used exceptions. Function call overhead is the major reason. As mentioned before, like RTTI, it's, in most studios, not a subject of discussion. Not because most coders come from a Java/academics background, because frankly, most don't.
It doesn't affect unit testing really as you just assert on conditions. For libraries, you're better off without exceptions as you'll force it upon everyone that uses it.
While it makes some situations slightly harder to handle, it also (imo) forces you to have a more controlled setup, as exceptions can lead to abuse. Error tolerance is nice, but not if it leads to sloppy coding.
Mind you, this comes from someone who never used exception handling (well okay, once or twice in tools - it didn't do it for me, I guess it's what you grow up with).
> 2 votes

# Answer
The most important thing for me as a professional games developer is that exceptions have to be written by people that understand how exceptions work (which there are few in the games industry) debugged by them too, and the underlying code that runs them (which is a branchy mess anyway and will kill your in-order processor) had to be written by people providing your compiler/linker. The problem with that is that they only have a finite amount of resources, so they concentrate on writing better optimisations and fixes for code that games developers do use... which usually isn't exceptions. If you've got an exception bug on modern hardware with new compilers, who are you gonna call? your exception expert who thinks everything is okay with the code, or the vendor who says, yeah, soon, we're just trying to make intrinsics happen more automatically.

There's nothing inherently wrong with exceptions, just they're not good because reality gets in the way of theory.
> 1 votes

# Answer
To me exception-handling can be great if everything conforms to RAII and you're reserving exceptions for truly exceptional paths (ex: a corrupt file being read) and you never need to throw across module boundaries and your entire team is on board with them......

**Zero-Cost EH**

Most compilers these days implement zero-cost exception handling which can make it even cheaper than manually branching on error conditions in regular execution paths, though in exchange it makes exceptional paths enormously expensive (there is also some code bloat from it, though probably not more than if you thoroughly handled every possible error manually). The fact that throwing is enormously expensive shouldn't matter though if exceptions are being used the way they're intended in C++ (for truly exceptional circumstances that shouldn't happen in normal conditions).

**Side Effect Reversal**

That said, making everything conform to RAII is much easier said than done. It's easy for local resources stored in a function to wrap them into C++ objects with destructors that clean themselves up, but it's not so easy to write undo/rollback logic for every single side effect that could occur in the entire software. Just consider how hard it is to write a container like `std::vector` which is the simplest random-access sequence to be perfectly exception-safe. Now multiply that difficulty across all the data structures of an entire large-scale software.

As a basic example, consider an exception encountered in the process of inserting items to a scene graph. To properly recover from that exception, you might need to undo those changes in the scene graph and restore the system back to a state as though the operation never occurred. That means removing the children inserted to the scene graph automatically on encountering an exception, perhaps from a scope guard.

Doing this thoroughly in a software that causes many side effects and deals with a lot of persistent state is much easier said than done. Often I think the pragmatic solution is to not bother with it in the interest of getting things shipped. With the right kind of codebase which has some kind of central undo system though and maybe persistent data structures and the minimal number of functions causing side effects, you might be able to achieve exception-safety across the board... but it's a lot of stuff you need if all you're going to be doing is trying to make your code exception-safe everywhere.

There's something practically wrong there because conceptually side effect reversal is a difficult problem, but it's made more difficult in C++. It's actually easier sometimes to reverse side effects in C in response to an error code than it is to do it in response to an exception in C++. One of the reasons is because any given point of any function could potentially `throw` in C++. If you're trying to write a generic container working with type `T`, you can't even anticipate where those exit points are, since anything involving `T` could throw. Even comparing one `T` with another for equality could throw. Your code has to handle *every possibility*, and the number of possibilities multiply exponentially in C++ whereas in C, they are much fewer in number.

**Lack of Standards**

Another problem of exception-handling is lack of central standards. There are some like hopefully everyone agrees that destructors should never throw since rollbacks should never fail, but that's just covering a pathological case that would generally crash the software if you violated the rule.

There should be some more sensible standards like never throw from a comparison operator (all functions which are logically immutable should never throw), never throw from a move ctor, etc. Such guarantees would make it so much easier to write exception-safe code, but we have no such guarantees. We have to kind of go by the rule that everything could throw -- if not now, then possibly in the future.

Worse, people from different language backgrounds look at exceptions very differently. In Python, they actually have this "leap before you look" philosophy which involves triggering exceptions in regular execution paths! When you then get such developers writing C++ code, you could be looking at exceptions being thrown left and right for things that aren't really exceptional, and handling it all can be a nightmare if you're trying to write generic code, e.g.

**Error-Handling**

Error handling has the disadvantage that you have to check for every possible error that could occur. But it does have one advantage that sometimes you can kind of check for errors slightly late in hindsight, like `glGetError`, to significantly reduce the exit points in a function as well as making them explicit. Sometimes you can keep running the code a little bit longer before checking and propagating and recovering from an error, and sometimes that can genuinely be easier than exception-handling (especially with side effect reversal). But you might not even bother with errors so much either in a game, maybe just shutting the game down with a message if you encounter things like corrupt files, out of memory errors, etc.

> How it pertains to the development of a libraries used through multiple projects.

A nasty part of exceptions in DLL contexts is that you cannot safely throw exceptions from one module to another unless you can guarantee that they are built by the same compiler, use the same settings, etc. So if you're writing like a plugin architecture intended for people to be used from all kinds of compilers and possibly maybe even from different languages like Lua, C, C#, Java, etc., often exceptions start to become a major nuisance since you have to swallow every exception and translate them to error codes anyway all over the place.

> What does it do to using third party libraries.

If they're dylibs, then they cannot throw exceptions safely for reasons mentioned above. They'd have to use error codes which also means you, using the library, would have to constantly check for error codes. They could wrap their dylib with a statically-linked C++ wrapper lib you build yourself which translates the error codes from the dylib into thrown exceptions (basically throwing from your binary into your binary). Generally I think most third party libs shouldn't even bother and just stick to error codes if they use dylibs/shared libs.

> How does it affect unit testing, integration testing, etc?

I generally don't encounter teams testing exceptional/error paths of their code so much. I used to do it and actually had code that could properly recover from `bad_alloc` because I wanted to make my code ultra-robust, but doesn't really help when I'm the only one doing it in a team. In the end I stopped bothering. I imagine for a mission-critical software that entire teams might check to make sure their code robustly recovers from exceptions and errors in all possible cases, but that's a lot of time to invest. The time makes sense in mission-critical software but maybe not a game.

**Love/Hate**

Exceptions are also my kind of love/hate feature of C++ -- one of the most deeply-impactful features of the language making RAII more like a requirement than a convenience, since it changes the way you have to write code upside down from, say, C to handle the fact that any given line of code could be an implicit exit point for a function. Sometimes I almost wish the language didn't have exceptions. But there are times when I find exceptions really useful, but they are too much of a dominating factor to me in whether I choose to write a piece of code in C or C++.

They would be exponentially more useful to me if the standard committee really focused heavily on establishing ABI standards which allowed exceptions to be safely thrown across modules, at least from C++ to C++ code. It would be awesome if you could safely throw across languages, though that's kind of a pipe dream. The other thing that would make exceptions exponentially more useful to me is if `noexcept` functions actually caused a compiler error if they tried to invoke any functionality that could throw instead of just calling `std::terminate` on encountering an exception. That's next to useless (might as well call that `icantexcept` instead of `noexcept`). It would be so much easier to ensure that all destructors are exception-safe, for example, if `noexcept` actually caused a compiler error if the destructor did anything that could throw. If that's too expensive to thoroughly determine at compile-time, then just make it so `noexcept` functions (which all destructors implicitly should be) are only allowed to likewise call `noexcept` functions/operators, and make it a compiler error to throw from any one of them.
> 0 votes

# Answer
As far as I see it there are two main reasons it's not traditionally used in game development:

* Most game programmers are either graduates, who learned on Java and Haskell, or C programmers, who don't have any experience of exceptions. Hence they're quite afraid of them and don't know how to use them correctly.
* The stack unwinding when an exception is thrown has performance implications (although this is kind of received wisdom, and some references would be great).
> -2 votes

---
Tags: c++, software-engineering
---


# Question
Title: Reading a text file and changing each digit into a value inside an array c#
I'm having a bit of an ordeal with the StreamReader.

I'm working on a game where you build the map with a 2D array by imputing different numbers so the array like this:

```
    int[,] map = new int[,]
    {
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,1,1,1,1,1,2,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,1,1,1,1,1,1,1,1,1,1,1,1,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    };

```

will give you the outcome where the 0's are one type of block and the 1's another and so on.

I currently have that working, however the array is hardcoded in.

What I am now trying to solve is how to read it from a text file. I attempted doing it in a Console Application with this code but I keep on receiving errors.

```
    static void Main(string[] args)
    {
        int[,] map = new int[300, 300];

        StreamReader SR = new StreamReader(@"F:\test.txt");

        for (int y = 0; y < 300; y++)
        {
            for (int x = 0; x < 300; x++)
            {
                map[y, x] = int.Parse(SR.ReadLine());
            }
        }
        SR.Close();

        for (int y = 0; y < 300; y++)
        {
            for (int x = 0; x < 300; x++)
            {
                Console.Write(map[y, x]);
            }
        }
        Console.ReadLine();
    }

```

Any idea how I can make it work for a 2D array so that whenever the compiler reads a digit, it allocates a number into a specific area in the array, so for example when a file like this is read:

```
11111
10001
10001
10001
10001
11111

```

It will turn into an array like this:

```
1,1,1,1,1
1,0,0,0,1
1,0,0,0,1
1,0,0,0,1
1,0,0,0,1
1,1,1,1,1

```

Thanks for any help provided. :)

# Answer
With `int.Parse(SR.ReadLine())` you are trying to convert the whole input line (consisting of 300 digits) into one single `int`. This does of course not work.

It is easier to read the file into an array of strings representing the lines all at once. No explicit opening and closing of files.

```
string[] lines = File.ReadAllLines(path);

```

Then you can access single characters of the line through an index

```
for (int y = 0; y < 300; y++)
{
    for (int x = 0; x < 300; x++)
    {
        map[y, x] = lines[y][x] == '0' ? 0 : 1;
    }
}

```

This also easily allows you to use more graphical characters like 'X' for walls.

```
map[y, x] = lines[y][x] == 'X' ? 1 : 0;

```

---

To be able to read maps of different sizes you can do

```
string[] lines = File.ReadAllLines(path);

int width = lines[0].Length;
int height = lines.Length;
if (lines[height - 1].Length < width) {
    height--;
}

int[,] map = new int[height, width];

//TODO: fill the map as shown above, but use width and height instead of constant 300.

```

If you hit enter after the last map line, you might get an empty last line. Therefore we subtract 1 if the last line is too short. This won't handle additional empty lines at the end.
> 3 votes

---
Tags: c#, xna-4.0, tilemap, text
---


title: GameMaker Studio 2 random isnt random

text:
# Question
Title: GameMaker Studio 2 random isnt random
I'm making a game where things randomly generate. It used to work, but now all the sudden they keep spawning in the same area every time. does anybody know a fix?

# Answer
You need to call `randomize` to set the seed to a random value

More here: https://docs.yoyogames.com/source/dadiospice/002\_reference/maths/real%20valued%20functions/randomize.html
> 1 votes

---
Tags: game-design, game-maker, random
---