# Question
Title: How can I make a beveled edge with bump mapping?
I say bump mapping for lack of a better term, but that may not be what I need. I'm trying to make my corners of various objects look bevelled as opposed to square:

I can't just create a physical bevel on all the edges (performance concerns), and I can't just apply soft shading (I want a hard, but beveled, edge), so I'm trying to figure out if there's a way with shaders / bump mapping to apply a beveled / tapered look to sharp edges to give them a bit of a blunt feel, or even appear to actually be tapered sharply rather than just blunt, but either way is fine.

How can I make an edge tapered / blunt with bump mapping / shaders?

# Answer
> 6 votes
The usual approach to this is to use your 3D software to create a “high” and “low”-detail version of your model, then bake a normal map that maps the details from the former onto the latter. For a simple example, take a look at this high-detail and low-detail version of a beveled square:

…followed by the baked normal map, and the low-detail square with the normal map applied to it:

Silhouettes will be visibly wrong at mesh corners, of course, since the low-detail version of the mesh doesn’t have the additional geometry there, but on continuous edges that don’t protrude from the object the result can be very convincing. As a bonus, thanks to texture filtering (sampling the normal map at locations “in between” its pixels), you’ll get some slight additional rounding at the edges of your bevels—note the highlight just below the top edge in the image above.

The exact process for this differs between 3D packages; in Cinema 4D you use a “Bake Texture” tag on the low-detail object, turn on Normals, and drop the high-detail object into the Source field, but in general you can search for “\[name of 3D software\] bake normals” and probably turn up the workflow for what you’re using.

---
Tags: normal-mapping
---


# Question
Title: How to swap between two player objects in Unity?
I have two object for the player. Whenever I press space I'd like to swap between them and also I would like to change the first player main camera to the second player camera and equally for the minimaps. It's the same as swaping a between characters in a LEGO game.
When I try this in the "Game" window, the camera should focus on the first player, but for some reason it doesn't. Neither does the first object move on WASD or on arrow keys presses. The second object is dead.
The cameras are basically a dirty trick and I really need only two. Both players have the same PlayerController script attached.

**PlayerController.cs UPDATED 10.01.2018 20:45 CET - Basically what I wanted to have**

```
using UnityEngine;

public class PlayerController : MonoBehaviour {

public float speed;

public GameObject playerAtDockCamera;
public Camera playerAtDock;

public GameObject playerAtSeaCamera;
public Camera playerAtSea;

public Rigidbody p1; //player object one
public Rigidbody p2; //player object two

private bool atSea = false;
private Rigidbody rb;
private Vector3 cameraposition;

void Start ()
{
    rb = p1;
}

private void Update()
{
    if(Input.GetKeyDown(KeyCode.Space))
    {
        atSea = !atSea;
    }
}

void FixedUpdate()
{
    float moveHorizontal = Input.GetAxis("Horizontal");

    float moveVertical = Input.GetAxis("Vertical");

    if (!atSea)
    {
        if (rb == p2)
        {
            rb.velocity = Vector3.zero;
            rb = p1;
        }
        EnableDock();
        rb.AddForce(new Vector3(moveHorizontal, 0.0f, moveVertical) * speed);
       }
       else
        {
        if(rb==p1)
        {
            rb.velocity = Vector3.zero;
            rb = p2;
        }
        EnableSea();
        rb.AddForce(new Vector3(0.0f, 0.0f, moveVertical) * speed);

 }
}
void EnableSea()
{
  playerAtDock.enabled = false;
  playerAtSeaCamera.SetActive(true);
  playerAtSea.enabled = true;

}
void EnableDock()
{
    playerAtDock.enabled = true;
    playerAtSeaCamera.SetActive(false);
    playerAtSea.enabled = false;

}
}

```

# Answer
> 1 votes
You should have the following setup:

1. One player controller script. This will always handle the input for the CURRENT game object (the one the script is attached to) and two player objects. One of these starts with its camera and player controller disaled.
2. Code that deals with the space bar.
3. When the space bar is pressed it gets the player controller from EACH1 player object and toggles the script's `enabled` property. It *also* enables or disables the camera associated with that player.

Trying to have the player script move both players depending on a flag in that script leads to both scripts moving the same player object (even if one is flagged on and the other flagged off) this is due to the way you've structured your `if (!atSea)` check: one of these will be true (moving `p1`) and the other will be false (moving `p2` ... which is a reference to *the other script's p1!*)

1 If the script that handles the space bar *is* the player controller, then it still needs to deal with both copies: if a script disables itself, it cannot re-enable itself because it's off! I recommend having this code in an unrelated script attached elesewhere (and only a single copy).

---
Tags: unity, c#, camera, control, single-player
---


# Question
Title: Are random events beyond players' control necessary for "strategy" games?
By "random event" I mean critical hits, misses, random variation in some kind of result etc. Examples of these include the accuracy mechanic in XCom; critical hits and accuracy chance in Darkest Dungeon; misses and fire/breech chance in FTL.

Something in common about these examples is that they are all games in which players have an indefinite amount of time to decide on actions. So, could it be that by adding random, RNG-based events, the game relieves the players' burden of feeling compelled to predict every possible outcome in the future? Could a game similar to the example do away with the randomness? If so, how could that change the experience?

# Answer
As other users have pointed out, there's **no requirement** to include random elements in a strategy game, and indeed there are many classic well-loved games that have no randomness at all (eg. Chess, Go).

For considering the **effect of randomness on the experience of play**, I'd highly recommend checking out **The Prototype that was Banned from Halfbrick**, a GDC talk by Luke Muscat, that goes into depth on what a lack of randomness can do to PvP competitive strategy games. (Stick around to the end where I circle back to the single-player case)

Specifically, in the eponymous prototype, and in a similar strategy game he discusses called Neptune's Pride, the cocktail of competitive non-random strategic mechanics tend to **foster an intensity of play that can be distressing to players**.

(Some choice bits: Neptune's Pride has been called "the most effective tool for ruining friendships," "an exercise in social devastation," and players have asked the creator to ban them from the game so they won't play it anymore. The Halfbrick prototype was reported to be "damaging the relationships I have at work" and players reported feeling "paranoid" when playing)

Some of the factors at play:

* the lack of random chance lets players develop **elaborate schemes with guaranteed results** \- freeing them to trap and **backstab** fellow players as much as they want with **no fear of repercussions**, knowing they can eliminate the aggrieved parties with 100% success.

+ Randomness can encourage players to weigh odds and develop contingency plans or hedge their bets more often, playing with a range of more moderate strategies, according to their personal risk tolerance.
* A player in a **losing position** can see it coming and **can't do anything about it** or hope for respite - they just get to watch as they're dragged through the grinder.

+ With the occasional lucky miss or miraculous critical, a player can cling to at least some ray of hope, and will occasionally be able to snatch victory from the jaws of defeat with a few good rolls at key moments, leading to dramatic reversals of fortune.
* There's no **"emotional safety valve" to blame the game rather than each other**, the way we might laugh off a lucky Blue Shell in Mario Kart or Final Smash orb in Smash Bros.
* Non-random mechanics put a **great deal of emphasis on player skill and making optimal decisions**. You can't muddle through and see what happens - if you end up on a losing path eventually, it's directly attributable to a mistake you must have made somewhere, so the pressure to analyze every move can be very high.

+ This can affect the game's **accessibility to a wide audience** and new players especially. In a game with significant randomness, players of different skill levels can play against each other and maybe both have a shot at winning, or at least feeling competitive with occasional successes along the way.

    In purely skill-based games, the more skilled player will almost always dominate, making it harder for new players to get onboard once a community of experienced players is established. (But, on the flipside, this can be very rewarding for those high-skill players, as match results are an honest signal of superior skill - great for leaderboard and tournament rankings)

Related to this, it's also worth noting a result from combinatorial game theory: if you have a game with sequential (non-simultaneous) turns, perfect information (no hidden board, hand of cards, or secret moves) and no randomness, then it's guaranteed to have a solution. That means that, at least in theory, you could write a game book of perfect moves "if your opponent does X, do Y" and if a player plays "by the book" then the **outcome of the game is pre-ordained**: either one player can always win no matter what their opponent does, or a player who can't win can force a stalemate.

Think of playing Tic-Tac-Toe, and how much less interesting it gets after you learn a few simple move-countermove patterns, leading to stalemates unless one player messes up.

Now, for any game of significant complexity, the "game book" often ends up being astronomically huge and impractical to compute, but even so **competitive play tends to gravitate toward memorization** of "good" moves (think of the books upon books of Chess openings and endgames or Go scenarios a player needs to study to be competitive at even a medium level). Having a large set of scenarios can dampen this temptation to memorize - see for example David Sirlin's Chess 2, which introduces multiple different armies, so memorizing moves for every possible match-up becomes less practical.

All of this is most pronounced in player-versus-player competitive play. But **similar patterns will arise in single-player games as well**, where a lack of randomness makes the game **increasingly like a puzzle**, where each level/challenge has a set of "correct" solutions (achieving the most points / least losses etc.), rather than a landscape of strategies with more nuanced risks & rewards.

Again, none of this says you must include randomness, they're just points to be aware of in how non-randomness vs randomness can influence the flavour and dynamics of the game.
> 11 votes

# Answer
No™

Example: Lords of Conquest on the C64 had a mode with zero random events. It was a land-conquest/resource management game. It was quite intense with serious diplomacy going on because if you didn't have enough force to win on your own, it was 100% impossible and you needed help.

Having no random elements certainly presents design challenges, but it's definitely possible.
> 4 votes

# Answer
It honestly depends on the type of game you want to make.

If you're making a game like XCOM, where players are in control of small, tactical squad of soldiers, not having RNG involved can quickly turn the game into something that isn't quite what you expected.

Bad example: imagine if XCOM did not have an accuracy mechanic, and all attacks had a 100% chance to hit and a 0% chance to score a critical hit. The game would simply be a matter of which side of the opposing forces had better damage and higher health. There would still be tactical elements like avoiding line of sight, but the game would no longer be about tactical battlefield control.

Instead, it would focus more on how well the player can build their squad by balancing how much in terms of control skills (mind control and panic, in XCOM), damage output, and maximum health the squad will have. Most of the strategy will be back-end: how skilled the player is at making a good team composition, how good they build the skills of each individual soldier, how quickly they can research, build, and equip upgraded armor and weapons, ect.

Although there is still a great deal of strategy involved without RNG in a game like XCOM, the set of skills the player must master shift from balancing risk vs reward and clever positioning to more RPG-centric skills like character building.

Also, there are many strategy games that don't use RNG at all. Most notably the Civilization series (although I may be mistaken), and many real-time strategy games like Warcraft III and Halo Wars.
> 3 votes

# Answer
> Could a game similar to the example do away with the randomness? If so, how could that change the experience?

The way I see it is that randomness is used for what the player cannot directly control. In an action platformer, you can control the player to a very fine degree: make him dodge things, jump over traps, etc using your reflexes and hand-eye coordination. In a turn-based game, the control is very coarse. No player is going to deliberately click on a trap to walk into. So what the player cannot control anymore in such a case is replaced with the analogical coin toss or dice roll, and I actually think that's perfectly fine and great.

Normally I don't think a game has to be realistic or resemble life at all to be fun, but here I think there's something interesting to note. Life is full of surprises. It's not entirely predictable, and it'd probably be boring if it was. We don't know if that girl we're going to ask out is going to agree. We don't know if we'll be hired for that job. We don't know if that programming idea that seems so promising is going to pan out. There's an element of chance in everything we do, and I think that's what makes things so fun, so dangerous, so surprising, and interesting. It seems to me like things would become incredibly dull if we took out that element of chance to the point where we could start predicting and perfectly calculating the outcome of everything we do while the world stops and waits for us to make a move.

I read a blog from a designer before who was determined to create a perfectly deterministic (as in lacking random events) turn-based game, and I couldn't help but disagree to a great extent with his thoughts for these reasons. That said, he made a very solid turn-based strategy game, but it felt to me more like a puzzle game where you're just kind of figuring out the optimal play against perfectly predictable and repeatable patterns. It changed the way the game felt considerably from other games like it which used random events and it wasn't quite my cup of tea even though I usually love those types of games. It starts to feel like playing chess, and not against a human player, but against a very predictable AI which always makes the exact same moves.

And that can still provide this kind of puzzle challenge to figure out those patterns and how to exploit and beat the AI after seeing it repeatedly do the same things over and over, but it feels very different, and it's not like learning enemy patterns in an action game. Action games which start revealing very predictable patterns are very interesting to me and I like determinism in action games, but there you never quite get the exact same result since it's too hard to repeat everything in perfect timing at the precise millisecond when you're controlling things in realtime, and it still feels like the game is taxing your reflexes and hand-eye coordination even when you know its patterns. With a turn-based game, you start seeing the *exact* same results repeating very quickly when it's perfectly deterministic while allowing you to do the exact same things every turn at your leisure, and that feels very different to the point where I'm wishing there's a fast forward button when I'm seeing the exact same things happen while repeating my previous moves up to a point.

But I could see where he was coming from. He wanted to avoid the analogical: 7 damage, 3 damage, miss, miss, miss, 1 damage, 3 damage, miss, miss... boring and frustrating! And in those cases when the RNG is just used to determine how much damage you do ranging from 0 (miss) to some other number, it can get quite boring and frustrating. In those cases I think just: 8 damage, 8 damage, 8 damage, enemy dies is already more fun.

Yet I actually think the problem there is that it's not random enough. It's boring. Imagine instead that snake eyes results in the player fumbling while the enemy gets a free counterattack, while boxcars causes an instant decapitation, and yo-leven causes you to stun the enemy, and there's always a chance that a clumsy player could trip and lose his turn just in the process of moving. I think that's considerably more interesting. It's not just outputting a number anymore. It's kind of like drawing a random card and reading what happens as a result.

I think this is what made games like Fallout really fun (or at least to me). A whole lot of different things could happen just by trying to shoot an enemy in the arm from glancing off and barely causing damage to making him drop his weapon to crippling him to the point where he can't use that arm or even blowing his entire arm off and killing him with a really lucky shot. That's interesting and really fun in ways that go beyond: miss, 2 damage, miss, miss, 7 damage, miss, 3 damage, miss, 1 damage...

So anyway, in my opinion turn-based games shouldn't be trying so hard to do away with randomness. I would prefer that more embrace and utilize it in more interesting ways than miss here and N damage there. If they do move away from randomness, then it does tend to change how the game feels considerably not that it's necessarily bad, but I would say it tends to push the game towards that kind of puzzle realm of gaming.
> 0 votes

---
Tags: game-design, game-mechanics
---


title: Importance of templates?

text:
# Question
Title: Importance of templates?
From a game developing point of view, how important do you consider templates to be as a topic to know about in C++? Have you used templates as a part of developing games or similar? Neither do I really understand how important templates can be considered from a *general* point of view.

# Answer
There are 2 aspects:

* Consuming meta-programming, i.e. using templates written by others: The STL (Standard TEMPLATE Library) is a pillar of C++. Nowadays, developing a large C++ application - that includes most games - without using template classes like `vector<>` or `shared_ptr<>` means the developer doesn't know how to program in C++.
* Producing meta-programming, i.e. writing templates: Oftentimes, one can get away without writing templates (often using polymorphism instead) by sacrificing a bit of performance, type safety, or both. If you want cutting edge performance, you need templates, if you don't, you can skip them. Additionally, due to the added type safety provided by templates, their use is strongly recommended if you write a library or other complex components that are to be used by others, as proper use of templates can make your interfaces easy to use right and hard to use wrong. In larger teams, it's common that some people write most of the template code, while most others merely use the templates.

Overall, if you don't want to write templates, C++ may not be the best programming language to chose. If you don't want the highest performance, you could use something like C# instead, unless you're choosing C++ because you're more familiar with the language. Yet if you're not familiar with templates, you're not familiar with C++. There are still plenty of valid reasons to chose C++ regardless, e.g. licensing, corporate constraints, supported target architectures, pre-existing libraries, etc.
> 4 votes

# Answer
Templates are a crucial part of C++, they enable flexibility and expressiveness without sacrificing type-safety or efficiency. They are C++'s implementation of generic programming.

They don't have any specific relationship to game development, but like all the other tools in the box they come in handy when you need them. They are typically more useful in "engine"-flavoured tasks, which need their characteristics, and less prominent in the gameplay code which sits on top and doesn't need to be fast or generic (that's also the part that can be written with a scripting language to get other benefits instead).

For an example, here is one of my answers about implementing a kind of component-based dispatching system. You can see that I've used templates extensively (and a hint of macros as well) to create a generic system, and then used it to write terser gameplay code.
> 1 votes

# Answer
Templates are especially useful for containers or similar types. Since you understand templates *generally* I will omit an explanation of them, and rather give an example instead.

Templates can be useful in game development (other than for simple containers) when using patterns like the object pool pattern, especially for particle pools. You might want to reuse the implementation for an object pool for different kinds of objects, like enemies, particles, or props. (The linked example does not use templates, but explains the pattern well.)

However, since this is mostly used for optimizing, it is mostly dependant whether one uses an engine that already abstracts instancing functionality, or one even wants to write a custom game engine, in which case it might be inevitable.
> 1 votes

# Answer
Depends what you mean by 'from a games development point of view'. I've developed games without using templates at all. I've worked for companies which insist on using the standard template library and encourage using templates as well as companies which ban stl & templates completely! If you would like to work in games development then its a good idea to understand them. When abused they can bloat code and make it less readable. Understanding their potential pitfalls is quite important.
> 0 votes

---
Tags: c++
---


# Question
Title: Gesture detection coordinates not synced with viewport
I am trying to implement pan(float x, float y, float deltaX, float deltaY) from GestureDetector . I set the coordinates of the texture to the parameters of the pan , so whenever i drag the texture on screen it draws there . it worked perfectly .

> Now i put a camera and a viewport in the screen and suddenly the the texture isn't following the drag coordinates properly .

here is the create() method where I initialise my camera and viewport

```
    @Override
public void create () {
    batch = new SpriteBatch();
    img = new Texture("badlogic.jpg");
    pos = new Vector2(0,0);

    camera = new OrthographicCamera();
    camera.position.set(width/2,height/2,0);
    viewport = new StretchViewport(width,height,camera);
    viewport.apply();
    gestureDetector = new GestureDetector(this);
    Gdx.input.setInputProcessor(gestureDetector);
}

```

and here is how i implement the pan method from the interface

```
@Override
public boolean pan(float x, float y, float deltaX, float deltaY) {
    pos.x = x ;
    pos.y = Gdx.graphics.getHeight() - y ;
    return true;
}

```

The code works fine when i am touching the top left corner of the screen where the Gesture detector considers the coordinate (0,0) but as I drift towards the right ,the texture drawn is somewhat ahead of the x coordinate being touched . It is working fine with respect to the Y axis .

# Answer
I havent checked what you are trying to achieve but if you say it worked fine before you added a camera and viewport then it probably has something to do with screen vs world coordinates.

I believe what you are looking for is `viewport.unproject()` or `camera.unproject()`, this will transform screen coordinates into world coordinates and it should work properly.

Addition:

> `unproject(Vector3 screenCoords)`
> Function to translate a point given in screen coordinates to world space.

source: Libgdx Camera Doc
> 0 votes

# Answer
pos.add(deltax, -deltay) ;

X and y are current mouse position. Delta is how much it has been dragged.
> 0 votes

---
Tags: java, libgdx
---


# Question
Title: Is single/double frame allocator suitable only for POD datas?
Let´s say I have a single frame stack allocator, so I´m using it for allocating memories for my temporary data.

```
size_t freeTilesSize = 10;
int* freeTiles = _allocator.allocate<int>(freeTilesSize);

```

The stack doesn´t save any conditional stuff about the memory it creates(it cares only about the size of the chunk so it knows the new header offset). I see this a good for using with POD data structures or classes with default destructor, however, is it usable also for bigger entities with some behavior at the destruction? At this moment, my function *rewind* only sets the header ptr to the start of the allocated block so it doesn´t call any destructors.

Am i doing something wrong? What was your approach?

# Answer
You have 2 options,

1. keep track of destructors that need to be called and call them on clear
2. Make sure that any object stored in the stack will only allocate from a allocator that will be cleared after (or at the same time) as the allocator it is allocated in and make sure it does not hold sole ownership to third-party-library handles that need a destructor.

The first is more foolproof while the second is a bit more error prone but you can use `std::is_trivially_destructible<T>` to make sure you only allocate types without a destructor.
> 4 votes

# Answer
> Is single/double frame allocator suitable only for POD datas?

Nope, as long as it allocates memory properly aligned for any user-defined type. That said, about construction and destruction of non-trivial types...

> \[...\] so it doesn´t call any destructors. Am i doing something wrong? What was your approach?

You are doing things exactly right if that's, indeed, a memory allocator.

An allocator shouldn't actually care about the data types it stores, or else it's more like a data structure than memory allocator. The memory allocator's job is simple: it gives you requested amount of bytes, often from a pool of memory already allocated in advance, to do with as you like, after which you might free it and return it to the pool to be used somewhere else. The only type-related concerns an allocator faces is alignment and size. If you are using type traits for anything more than figuring out alignment and size, that's no longer resembling an allocator.

For your case:

```
int* freeTiles = _allocator.allocate<int>(freeTilesSize);

```

... the only purpose I see to making `allocate` a function template is to avoid a cast and avoid specifying type size/alignment. If it's a genuine allocator it shouldn't bother constructing whatever type, `T`, is. That's up to the client to do.

**Double Construction/Destruction UB**

You'd actually make your allocator far, far less general-purpose if you attempted to construct elements and destroy them through it, because imagine what happens if you tried to make `std::vector` use your allocator. `vector` would attempt to allocate with your allocator which would construct elements, and then `vector` would then try to construct them a second time. Likewise when you attempt to destroy the vector, it would attempt to destroy all the elements it contains and then free the memory, at which point your allocator would want to destroy them a second time. It's not the job of an allocator to be constructing and destroying elements. That's the job of the data structure.

It's for these reasons that `std::allocator` and practically all other allocator designs, widely-used, do not construct or destroy elements, since the point of an allocator is to be used by something that does if that's necessary, like a data structure.

Probably the result of this confusion between an allocator and data structure's responsibility is because of the nature of default `operator new/new[]` and `operator delete/delete[]`. The former carries the responsibility of *both* allocating and constructing elements, and the latter both destroying and freeing elements. But that's kind of for convenience. These operators shouldn't be considered allocators (and default `operator new/new[]` generally use `malloc` under the hood, which is an actual allocator and does not bother to construct things). Also none of the standard library containers use default `operator new[]` because that would make them redundantly default-construct elements. They rely on `std::allocator` instead which also does not construct/destroy elements while they manually construct and destroy elements themselves.

**Allocating `N` Elements != Constructing `N` Elements**

This separation of responsibilities between, say, data structure and allocator isn't an arbitrary separation of concerns but actually a fundamental requirement. For example, a data structure might want to allocate 1 kilobyte even though only half of that kilobyte is used to store and construct elements in the container. That's a common scenario with `std::vector` which often allocates more memory than needed to store its elements to avoid a memory allocation every time you insert to it, so it doesn't actually want to construct a kilobyte's worth of element data in that case (maybe only a fraction of it). This will be the case for any data structure which has something like a `capacity` concept separate from `size` (unrolled lists, deques, n-ary trees, hash tables, etc. etc. etc) which is generally any variable-sized data structure that doesn't allocate one element at a time.

If the allocator design favored constructing N elements when requested to allocate memory for N elements, it would make it impossible to implement `std::vector` let alone any variable-sized sequence or associative container which doesn't allocate one node at a time unless you don't mind constructors being called on elements you never inserted into the container, e.g. It is very, very important and useful for an allocator *not* to construct and destroy elements.

Among the variable-sized standard library containers, only a handful like `std::list`, `std::set`, and `std::map` could be implemented using a memory allocator that constructed and destroyed elements itself.

**Data Structures vs. Allocators**

Now if you are creating a data structure, that's a considerably higher level concept dealing with elements of a particular type rather than raw bits and bytes as with the case of an allocator. And in a C++ data structure, you should properly copy-construct or move elements inserted or emplaced with `placement new` and invoke their destructors manually on removal for non-trivial types (potentially using type traits as an optimization detail to skip that for plain old types) if you want to make them widely applicable, but a memory allocator has no such requirements.

And I actually recommend focusing more on data structures for performance than allocators, since splitting efficient memory allocation away from the data structure is always considerably more fiddly than having a data structure which just allocates memory efficiently without the help of an external allocator. Life becomes a lot simpler if you use a tree structure like a quad-tree or octree which just very efficiently allocates its nodes against any general-purpose allocator instead of relying on a separate allocator to be specified to have any hope of being reasonably efficient while it attempts to allocate one node at a time.

But for allocators, all you're concerned with is bits and bytes, so it shouldn't matter whether you're allocating things that are trivially constructible or not or deallocating things that are trivially destructible or not. That's not a concern for allocators to deal with. It's for the data structures. So your allocator should be suitable for allocating any data type provided it allocates bytes of memory to store them with proper alignment and size, but it would be up to the client to make sure that elements are constructed and destroyed properly after allocation and prior to freeing.

**Questions**

> I see this a good for using with POD data structures or classes with default destructor, however, is it usable also for bigger entities with some behavior at the destruction?

Again an allocator should not be concerned with construction and destruction, just as `malloc/free` aren't along with variants (`jemalloc`, e.g.), and just as `std::allocator` isn't. However, the client has the responsibility to properly construct and destroy elements as needed. Naive example assuming `Foo` is not trivially constructible and destructible:

```
// Allocate memory for Foos (not constructing them):
Foo* foos = stack_allocator.pop<Foo>(num_foos);

// Construct Foos:
for (int j=0; j < num_foos; ++j)
    new(foos + j) Foo(...);

// Do stuff with Foos.
...

// Destroy Foos:
for (int j=0; j < num_foos; ++j)
    foos[j].~Foo();

// Free memory, pushing it back to the stack.
stack_allocator.push<Foo>(num_foos);

```

However, aside from the above code being tedious to write, it also may not be exception-safe. So often you'd want to make it conform to \`std::allocator to allow standard library containers or create some kind of data structure which uses your allocator, like so:

```
// Allocate and construct Foos.
StackArray<Foo> foos(num_foos, stack_allocator);

// Do stuff with Foos.
...

// Destruction and memory freeing is done automatically
// when 'StackArray' goes out of scope.

```

> I would need to store them into heterogenous container and that would affect performance. No?

Just noticed this part in the comments but depends on the container and it doesn't have to be heterogeneous. If you really like the concept a stack frame allocator, then you can build some general-purpose containers against it like:

```
StackArray<Foo> array(alloc, size);

```

The only conceptual overhead is that it does need to store the size of the array as a data member since it needs that to destroy all the `Foos` in its dtor. And in the constructor it can construct all the `Foos` in the array and in the destructor it can destroy them. If `Foo` is trivially destructible or constructible, it can skip all that using type traits to determine whether that's needed or not at compile-time.

Just be a bit careful with data structures you create against a stack frame allocator, since their lifetimes should not persist beyond that of the allocator. And naturally the only data structures you can effectively create are ones that would not free memory themselves directly or only free memory in precise reverse order. Often what I suggest if you want a persistent stack frame allocator is to not make any data structures that use it free memory (or ignore their requests). Instead just do something like this:

```
void some_func(StackAlloc& stack_alloc, int n)
{
     ScopedAlloc scoped_alloc(stack_alloc);

     // Important: 'scoped_array' uses ScopedAlloc, not StackAlloc.
     ScopedArray<Foo> scoped_array(scoped_alloc, n);

     // Do stuff with 'scoped_array'. ScopedAlloc ignores any requests
     // from ScopedArray to free memory.  ScopedArray does,
     // however, invoke destructors when it is destroyed.
     ...

     // Meanwhile when 'scoped_alloc' goes out of scope, it frees
     // any memory chunks allocated through it in reverse order
     // from 'stack_alloc'.
}

```

> \[...\] however, is it usable also for bigger entities with some behavior at the destruction?

If you cover the destructors through data structures like the above, sure. That said the main thing to keep in mind about any kind of stack allocator is that it needs to free memory in the precise reverse order in which it is allocated. It can't free elements from the middle, e.g., so you generally need to tie everything to be allocated and freed to the local scope of a function which will take care of making sure memory is pushed/popped in a proper LIFO pattern.

> What was your approach?

I generally avoid stack allocators since they're a bit fragile in the ways described above if you aren't careful to tie your objects to the scope of a function to the point where it starts to feel like we're fighting the programming language and need a new one that allows the analogical equivalent of variable-length arrays in C. Instead the way I avoid heap allocations for common cases is doing something like this:

```
// 'n' is, 99% of the time, in the range [0, 64)...
void func(int n)
{
     int stack_mem[64];

     // Use stack_mem if the data fits, otherwise use heap.
     int* data = (n <= 64) ? stack_mem: new int[n];

     // Do stuff with data.
     ...

     // Free the memory if it was allocated on the heap.
     if (data != stack_mem)
         delete[] data;
}

```

... which you can generalize to a RAII-compliant, exception-safe data structure which properly invokes ctors/dtors if necessary like:

```
template <class T, int FixedBufferSize>
class SmallVector
{
public:
    ...

private:
     // Used to store data if it fits. We do not store
     // an array of T[] here since that would want to
     // invoke the default ctor on all of them. We only
     // want to construct elements which are actually
     // inserted to the container.
     typename std::aligned_storage<sizeof(T), alignof(T)>::type buf[FixedBufferSize];

     // Points to 'buf' if data fits, heap otherwise.
     T* data;

     int num:
     int cap;
};

```

... at which point the above turns into simply:

```
// 'n' is, 99% of the time, in the range [0, 64)...
void func(int n)
{
     // Only uses heap if 'n > 64'.
     SmallVector<int, 64> data(n);

     // Do stuff with data.
     ...
}

```

It's not as theoretically optimal as a stack frame alloc since it has to anticipate common cases and it could reserve more stack space than necessary (too much stack or too little -- both would not be ideal), but it's so much less delicate. It can't be misused nearly as easily. You can even safely store these persistently if you want and treat it interchangeably with `std::vector`, only it doesn't heap allocate unless you insert more elements than you reserved through `FixedBufferSize`.

I actually prefer sequential allocators which only purge all memory allocated over a stack allocator that requires a strict LIFO push/pop pattern, since that can be so, so delicate when the language doesn't give us the tools to make sure we allocate and free in that precise order at all possible times.

**Stack Allocators**

Again IMO stack allocators are easy to misuse so I tend to avoid them, but one of the most interesting things about allocator proposals from Alexandrescu is that he generalized the concept of a "parent allocator". That is, every allocator can recursively use another allocator to allocate its own memory pool.

A stack allocator as a parent allocator becomes a lot more interesting, because you might implement a free list which actually does allow freeing elements in any order using a parent stack allocator for its pool, or vice versa.

But anyway, a single/double frame allocator is perfectly capable of allocating memory for UDTs, provided that it's allocating memory properly aligned for that UDT. Just make sure your stack pointer is aligned properly before you return its address for the client to use. But again you do need to properly construct and destroy those elements somewhere else, but that's not the concern or job of an allocator. It just deals with things at the level of bits and bytes, not data types.
> 0 votes

---
Tags: c++, architecture, game-loop, memory-efficiency
---


title: Disabling a script from another script

text:
# Question
Title: Disabling a script from another script
I have a script that is attached to many game objects. The script simply makes objects drag-able. I want this script to be disabled until a button is pressed.

I have used the below code to successfully find one of the game objects that the code is attached to:

```
    public class pressLoadBtn : MonoBehaviour {

    void OnMouseDown()
    {
        Debug.Log("LOAD BTN PRESSED");

        GameObject HB3 = GameObject.Find("HeavyBall3");
        draggableObject DraggableObject = HB3.GetComponent<draggableObject>();
        DraggableObject.enabled = false;
        Debug.Log("draggableObject script enabled is : " + DraggableObject.enabled);
    }
}

```

The console says that this script has been disabled but I know it has not been disabled. If the script had been disabled then I would not be able to drag the game object called 'HeavyBall3', but I can drag it.

Any ideas? I've tried shouting at the screen but that hasn't worked (yet).

# Answer
For the love of pancakes! I solved it...

It turns out that '.enabled' only affects the calling of Start, Update, FixedUpdate and OnGUI (I got that info from Bunny83 on this thread: https://answers.unity.com/questions/694778/cant-uncrosscross-a-script-component.html

It means I can't use 'OnMouseDrag' in my draggableObject.cs to drag objects but atleast I can move on with my life now! 3 days wasted! 3 days! Do you know what I could have done with 3 days? I could have built a model ship in a bottle! I could have cleaned the gutters. I could have fixed the lawnmower. But no, I found out that '.enabled' isn't all it's cracked up to be.

And just so you know, draggableObject.cs code is:

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

[RequireComponent(typeof(CircleCollider2D))]

public class draggableObject : MonoBehaviour
{
    public Camera cam;
    public Transform ball;
    public Rigidbody2D r;

    void OnMouseDrag()
    {
        Vector3 pos = Input.mousePosition;
        pos = cam.ScreenToWorldPoint(pos);
        r.velocity = (pos - ball.position) * 12;
    }
}

```
> 0 votes

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


# Question
Title: How to calculate Camera "correct" position and distance to Frame all my Scene?
Consider I have N dynamic points on my Scene, I would like to "frame" all them, with my Camera.

How can i calculate (at runtime) Vector3 Position to correctly frame all my scene ?

This is my idea:

1. Calculate Avarage for all my points
2. Move my Camera "up" to correctly "frame" all my points (i don't know how)
3. Use Unity LookAt(myAvaragePoint)

Thanks

# Answer
So there's effectively an infinite number of points which would qualify. Even if we assume that there's a single distance value which satisfies your problem (as any distance *greater* than that also works! But we will assume that you want the *smallest* distance for which this works), that still leaves every possible *rotation* around which we could orbit the camera and maintain all points in view.

That said, here's the approach I took:

1. Find the average center for all points. A better solution would be to compute the *geometric* center1 (so 40 points that are located very far out don't have any more impact than *one* point far out) but the raw average was easier for this sample and sufficient for the "hard part" (your step 2).
2. Move the camera to this point, then move it up 1 unit, and then move it backwards (`-1 * transform.forward`) 1 unit, then look at the average center point.

* This offsets the camera from the average so that when we start moving the camera away from the group we don't have to reorient the view: we already know this is the center and we will just move the camera backwards until all points are visible
3. Find the on-screen pixel coordinates of each point in the data set. If any of the values are negative, they are outside our view! Additionally, if the X or Y values are greater than the size of the screen, they are outside of the view in that direction too.
4. Loop: move the camera backwards 1 unit, recheck on-screen values. Repeat until all points are on screen.

And that gives us this:

```
using UnityEngine;

public class FocusInOnAll : MonoBehaviour {
    public Transform[] allPts;

    // Use this for initialization
    void Start () {
        Vector3 averageCenter = Vector3.zero;
        bool wasAnyPointOutside = true;
        foreach(Transform t in allPts) {
            averageCenter += t.position;
            Vector3 v = Camera.main.WorldToScreenPoint(t.position);
            Debug.Log("Point at: " + v);
            if(v.x < 0 || v.y < 0 || v.z < 0 || v.x > Screen.width || v.y > Screen.height) {
                wasAnyPointOutside = true;
            }
        }
        Debug.Log("Center: " + averageCenter / allPts.Length);
        Camera.main.transform.position = (averageCenter / allPts.Length) + Vector3.up - Camera.main.transform.forward;
        Camera.main.transform.LookAt((averageCenter / allPts.Length));
        while(wasAnyPointOutside) {
            wasAnyPointOutside = false;
            Camera.main.transform.position = Camera.main.transform.position - Camera.main.transform.forward;
            foreach(Transform t in allPts) {
                Vector3 v = Camera.main.WorldToScreenPoint(t.position);
                if(v.x < 0 || v.y < 0 || v.z < 0 || v.x > Screen.width || v.y > Screen.height) {
                    wasAnyPointOutside = true;
                }
            }
        }
    }
}

```

1This would be done by keeping track of the *minimum and maximum* X and Y values, then averaging the min and max together.
> 4 votes

# Answer
If you are not too worried about performance you could probably go for an iterative process. Following the steps you mentioned:

1. compute average position
2. LookAt(average position)
3. move camera along its -transform.forward axis by a fixed step, until the condition is met.

The condition is that all points are within view: one way to do it is to iterate on every point and check if the screenspace position is between 0 and 1 on both axis. (https://docs.unity3d.com/ScriptReference/Camera.WorldToViewportPoint.html)
> 2 votes

---
Tags: unity, algorithm, camera
---


# Question
Title: Character keeps falling through the terrain and jittering
I honestly don't know what the problem could be anymore. I have a humanoid character with animations, and a charactercontroller.
I also have a ragdoll (seperately) that only follows the animations through script (doesn't do anything else). the ragdoll has a script on both feet, with colliders and rigidbody's, and sets a bool to true when either of them hits something. It also has an update function that casts a ray, and sets that same bool when it hits something. this way i know if it is grounded or not. the charactercontroller is also used to see if it is grounded or not.

In my control script I translate the character downward when it is not grounded, and set that gravity vector to 0 if it is.

the collisions work, the raycasts work, and the charactercontroller work, but still the character falls through. i've also tried increasing the solver settings, turning off auto simulation and PCM, increasing the contact offset to the point where it floats above the ground, and still falls through.

All the scripts use update functions, but the behaviour is the same in FixedUpdate. I tried with and without rigidbody's in the charactercontroller, and with and without charactercontroller itself.

this part of code is for movement:

```
bool walking = skaterParams.walking;

            if (walking && !Onboard && !Helper.bailing) {
                moveDirection.y = 0;

                moveDirection = new Vector3(Input.GetAxisRaw("Horizontal"), 0.0F, Input.GetAxisRaw("Vertical"));
                moveDirection = transform.TransformDirection(moveDirection);
                moveDirection *= speed;
                if (Input.GetKeyUp ("joystick button 1")) {
                    moveDirection.y = jumpSpeed  ;

                }

            }

        if (!walking && !Onboard) {
            moveDirection.y -= gravity * Time.deltaTime;
        }
        if (!Onboard  && !Helper.bailing) {
            Char.transform.Translate (moveDirection * Time.deltaTime * 10);
        }

```

i could also share the code for seeing if he is grounded, but i'm trying to limit the post here, to not have too much text. I just know it works, but it's just not consistent. When setting auto simulation to true, the ragdoll is also extremely jittery... the ragdoll and character are on seperate layers and cannot collide. The raycasts have a layermask set to the terrain layer.

# Answer
> 1 votes
I haven't actually found the solution but it did get fixed somehow. after I restarted unity, all was still buggy and jittery and not working, then i tested it with the animator turned off. and it worked again. after that, i turned it back on, and it still worked. So i'm guessing the problem was with the unity engine itself somehow. I'll try to see if i can reproduce it, and find a fix, if anyone has the same problems.

---
Tags: unity
---


# Question
Title: Why does my rendering not correspond with my Box2D world?
I've decided to try to use the Box2D physics engine in my game, and as I started I'm facing weird behaviour. I've followed a video tutorial where we setup the Box2D world with world gravity, and then create an entity containing the collider.

Here's how I'm creating the entities:

```
void PhysicsEntity::init(b2World* world, vec2 position, vec2 dimensions)
{
    _body = createComponent<pin::WorldComponent>(this);
    _body->initWorld(position);

    _sprite = createComponent<pin::Sprite>(this);
    _sprite->initRender(dimensions, pin::TextureManager::loadTexture("crate.png"), _body);

    //PHYSICS STUFF
    b2BodyDef bodyDef;
    bodyDef.type = b2_staticBody;
    bodyDef.position.Set(position.x, position.y);

    _physics = world->CreateBody(&bodyDef);

    //Fixture&Shape
    b2PolygonShape boxShape;
    boxShape.SetAsBox((dimensions.x) / 2.0f, (dimensions.y) / 2.0f);

    b2FixtureDef fixDef;
    fixDef.shape = &boxShape;
    fixDef.density = 10.0f;
    fixDef.friction = 0.3f;
    fixture = _physics->CreateFixture(&fixDef);
}

```

Here's the render function:

```
void PhysicsEntity::render(pin::SpriteBatch* batch)
{

    mat4 modelMatrix;
    vec3 position(_physics->GetPosition().x, _physics->GetPosition().y, 0.0f);

    modelMatrix = glm::translate(modelMatrix,position);
    modelMatrix = glm::rotate(modelMatrix, glm::radians(_physics->GetAngle()), vec3(0.0f, 0.0f, 1.0f));

    _sprite->render(batch, modelMatrix);
}

```

It looks like this with Box2D debug rendering turned on:

Here's a video of how it behaves.

It looks like the collider and sprites locations differ. I've read that I shouldn't use 1 pixel = 1 meter ratio, but in many tutorials it was working without problem so I'm wondering if I forgot something.

The step settings I'm using are:

```
_physicsWorld->Step(1.0f / 60.0f, 6, 2);

```

What have I missed?

# Answer
The position of a Box2D body (from `GetPosition`) is its **center**, but your sprite rendering assumes the position is the **bottom-left corner**.

To correct this, render sprites with offsets of *{ x: width / 2, y: height / 2}*.
> 1 votes

---
Tags: c++, physics, box2d
---


title: How does 2D positioning works in Unity?

text:
# Question
Title: How does 2D positioning works in Unity?
I set two sprites with different widths on my scene, both on position x = 0, but the smaller one stays exactly at the middle of the bigger one. So, is the position x = 0 relative to the middle position of the sprites? Is there anyway I can set it to the top left (so my calcs would be easier)?

# Answer
The alignment of sprites is controlled by their Pivot point.

When your sprites are single images, you set the pivot in the import settings of the texture asset:

When it is a spriteset with multiple images, you can set the pivot individually for each sub-sprite in the sprite editor.
> 4 votes

---
Tags: unity
---


# Question
Title: When to Use Spatial Hashing vs Bounding Volume Hierarchy?
I've been slowly working on implementing a spatial hashing function into Bullet Physics to see how well it will work in my game engine as a general use. Though as I'm starting to design it, I do notice a few select problems about it's design.

So in the middle of research, I see that Spatial Hash functions start to suffer when objects take up too many cells.

Example: 1D's optimal case is at max 2. 2D's optimal case is 4. And 3D's optimal case is at most 8.

I can use a hierarchal method and hash larger objects to other tables to solve this.

But my biggest concern is exactly what are the best use cases for each of them?

BVH seems like it can generate a larger number of checks, and needs to bounce around on pointers

And Spatial hashing seems like it chews through memory, but is pretty good at what it does.

# Answer
> 4 votes
I believe this is largely dependent upon the implementer as well as preferred usage patterns (which can also depend on the implementer) as well as required usage patterns (which depend on domain).

**Construction**

As you pointed out, a spatial hash or grid can become very sub-optimal if elements are stored in a large number of cells. Hopefully you aren't duplicating the element data in that case, only indices, e.g., but it can still get explosive if you had to insert the analogical object into 100 cells as opposed to 1.

A BVH, on the other hand, can be costly to build since it can spend considerably more time determining how to split a node, especially if it's trying to achieve the best search quality using SAH, e.g. As a result even little old me can implement a grid accelerator (similar to spatial hash) in a small fraction of the time that even Intel's Embree with its cutting-edge fast SAH construction can build given the same million-triangle scene input (not saying mine would be better for raytracing, mind you, not even close).

**Searching**

For search times, I would generally think a well-implemented BVH has the theoretical edge unless your search queries just end up looking at a handful of cells on average. While the BVH does require descending down the tree and branching on each node, it's potentially skipping a whole lot of analogical cells that you might otherwise have to check with the spatial hash. If we can ignore construction times and focus predominantly on search times, I would think the well-implemented BVH would generally have a huge edge in many real world usage scenarios involving non-trivial searches on complex and varied data.

**Use Cases**

> But my biggest concern is exactly what are the best use cases for each of them?

Again I don't think you can avoid a subjective answer for this one, but I actually find a grid to be my number one go-to structure for spatial partitioning, using it until I find a reason not to do so.

One of the reasons is because in most of my use case scenarios, construction time is not anywhere close to being divorced from critical execution paths. Often I need to build/update the structure almost as often if not as often as I'm searching it.

The other reason is because of my own programming abilities and lack thereof. I'm not Ingo Wald publishing R&D on the most cutting-edge BVH construction techniques (and I can still beat him if we're only timing construction). I'm not a GPGPU wizard who has figured out how to store n-ary BVHs and construct them and search them super fast on cutting-edge GPUs. I'm just a C and C++ programmer who can do a competent job when it comes to efficient memory allocation and access patterns and apply some multithreading here and SIMD there. Because of this, if I was expected to make something very competent in a week to accelerate object/object intersection for a commercial product, my probability of doing a decent job is much higher if I go with a grid instead of a BVH.

There are countless papers on how to implement BVHs using the most cutting-edge techniques, and far fewer on spatial hashes and grids. That's not necessarily because spatial hashes and grids are always sub-optimal, but because implementing them very efficiently doesn't take a wizard like Ingo Wald. It's not a PhD-level data structure to publish papers about implementing efficiently unless you are doing something very different and interesting like using a hierarchical spatial hash hybrid.

Generally if you find construction and updating the structure to be almost as time-critical if not more and you're like me, then you might get a lot more mileage out of a grid (see below about "grid" vs. "spatial hash"). If you find your critical execution paths heavily skewed towards searching, as in the case of a raytracer, or you're just so much better at implementing a BVH than I am, then you might get more mileage out of a BVH.

**Search Patterns**

Another reason I might find more use for a grid is because my search patterns use the data structure directly. Instead of:

```
for each element in scene:
    // Use spatial structure to determine collision.

```

... which I see many people do, I instead do:

```
for each cell in spatial structure:
    // Mark elements that collide in cells.

```

That avoids evicting the same cells over and over, keeping that memory hot and inside a cache line, and if I need rapid searches, I make sure the data for a cell and inside a cell is contiguous. If I used the previous technique for traversal, I would think the BVH again would show a bigger edge, because it can potentially keep hitting the same nodes towards the top of the hierarchy whereas the previous access pattern using a spatial hash might be accessing cells all over the place, evicting them from a cache line only to reload them again in a single loop.

**Grid vs. Spatial Hash**

That said, you might have noticed I use "grid" a lot. Some people refer to the idea of a grid interchangeably with a spatial hash, but I find more use for what I call a "grid".

The distinction I make is that a spatial hash is often considered to be hashing data in 2 or more dimensions into a 1-dimensional data structure. It's also often sparse. The data structure might take less memory than is needed for a dense representation or it could take considerably more, just as with a hash table.

I have found in my use cases that I can implement a more performant solution with a "sorta dense" grid, and one that stores multiple instances of a data structure. For example, I might do this for a 3-dimensional grid:

```
struct Slice
{
    // Cells stored in this 2D "slice".
    std::vector<Cell> cells;

    // Elements stored in this 2D "slice".
    std::vector<int> elements;
};

struct Grid
{
    // 2-dimensional slices that make up the grid.
    std::vector<Slice*> slices;
};

```

And sometimes even:

```
struct Row
{
    // Cells stored in this 1D "row".
    std::vector<Cell> cells;
    std::vector<int> elements;
};

struct Slice
{
    // Rows stored in this 2D "slice".
    std::vector<Row*> rows;
};

struct Grid
{
    // Slices stored in this 3D "grid".
    std::vector<Slice*> grid;
};

```

As well as sometimes:

```
struct Row
{
    // Occupied range of cells stored in this 1D "row".
    std::vector<Cell> cells;
    std::vector<int> elements;

    // Position of first occupied cell in row.
    int first_occupied;
};

```

I don't actually use vector typically but the above is just a simple illustrative example, and generally `sizeof(Cell)` in my cases is 32-bits or less so it's cheap to store them by the millions. That involves more heap allocations for each 2D "slice/row" of the 3D grid, but it allows me to just store a null pointer for slices/rows which are completely empty (making it "pseudo-sparse") and if the traversal patterns are one row of each slice at a time, then often the entire data of interest for the cells and elements can fit in L2 or L3. It also means I can build a separate grid in each thread given a chunk of elements and then efficiently do a multithreaded merge of all the grids that each thread outputs to produce one final grid since the merge can merge rows/slices per thread without any shared data.

So I've gotten the most use of that for my use cases. Just to recap:

1. The answer depends heavily on the implementer, preferred usage patterns, etc.
2. The BVH most likely has the theoretical edge in most use cases for searching.
3. The grid and spatial hash probably has the theoretical edge in most use cases for construction and updates, at least if you can ensure that you aren't inserting each object into a boatload of cells with a cell size way too small for the common case element size.

Naturally the spatial hash and grid is also very obviously ideal even for searching if you are just, say, storing points and only searching for coincident points. There you're only going to be looking in one cell for an entire search for coincident elements, skipping the need to descend down the tree. That's a very specialized use case, however.

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


title: OpenGL Shadowmaps Limit

text:
# Question
Title: OpenGL Shadowmaps Limit
I would like to render an OpenGL scene with an arbitrary number of point lights (at least 1024) with shadows enabled.

My current method of rendering shadowmaps, however, cannot do this.

Let me explain

There are only 32 textures you can pass to a fragment at a time.

I am using 31 of those 32 textures for shadowmaps at the moment.

pseudocode for my main code...

```
setShader("DepthBufferPointLight", -1); //the int is actually numlights, used for deciding whether or not to recompile a finalpass shader. Irrelevant in this stage and set to -1 for debugging purposes.
FBO fBO* = CreateFBOs[6 * numLights]
for (int j = 0; j < 6; j++)
for (int i = 0; i < 6; i++)
{
 setRenderTarget(fBO[i]);
 setupCameraforLight(j,i); //Move the camera to the right position
 renderSceneDepth(); //Textures aren't even rendered for this
}
setRenderTargetDefault();
setShader("FinalPass", numLights); //The shader dynamically recompiles for final pass calls if the number of lights has changed, because it will need to change how many uniform struct lights there are.
setLightTextureUnits(fBO, 6, numLights); //glActiveTexture calls and glBindTexture calls
renderSceneFinalPass(); //Textures and uniforms are all set up for this, also does the lights

```

and then in the shader pipeline I do my calculations using the shadowmaps. My pseudocode is rough but you get the picture.

(SIDE NOTE: the dynamic recompiling is actually really simple and only changes one line of the shader, and I'm going to deprecate and remove the function once I figure out how uniform variable arrays work...)

my code breaks after numlights\*6 is greater than 31.

Is there a better way to do this?

my ultimate goal is to render an arbitrarily high number of point lights using shadow mapping

# Answer
Do you hit this limit when you do the light-pass or main render-pass?

With so many lightsources, I assume that your shadowmap resolution is very low?

The thing I would try first is to put all the shadowmaps in a shared large texture, like an atlas.

E.g, in a 8192x8192 texture, you could tile 16384 shadowmaps of 64x64 texels each.

In your main shader, you would simply calculate a texel offset for each of the shadowmaps.

That said, 1024 lightsources seems very high. Because you need to render the shadowmaps (views from the lightsource) for each of them. That would mean at least 1024 render passes over your scene. Or in your case even more, as your light sources seem to be omnidirectinal, as you render 6 views per light?

Maybe I make different assumptions on shadowmaps than you do. The way I do shadow maps, is to render the scene twice.

First I render the scene from the point of view of the light source, storing depths in a depth texture.

Second I render the scene from the point of view of the camera, using the shadowmap previously generated.

With 1024 lights, I would expect that your first pass needs to be done far too many times?

**UPDATE**: I wonder if `GL_TEXTURE_2D_ARRAY` would work as well as a work around of sampler limit.
> 2 votes

---
Tags: opengl, glsl, shadow-mapping
---


title: Drawing triangles from 3D triangulation

text:
# Question
Title: Drawing triangles from 3D triangulation
I'm trying to trianglulate 3D Points using DirectX11, so I triangulate 3D points then I try to draw triangles, the outcome of triangulation is std::vector, each Tri has a,b,c 3 values.

I don't see any output, I think I have a problem with the math..

here is my code:

```
void SetupTestVertices(ID3D11Device *pd3dDevice) {
    SimpleVertex *ptrV;
    int i;
    float *ptrToPoints;
    float scaleFactor = 1.f / (MAX_RAND * 0.5f);     // the test points are from 0 to MAX_RAND, so scale to 0 to 1.0
    int xyOffset = (MAX_RAND / 2);
    float brightness;                             // to make the triangles visually different from one another
    std::vector<R3> pts, pts2;
                              // to make the triangles visually different from one another

                               // create a random set of points to test the triangulation fuction
    if (g_numTestPoints > MAX_TEST_POINTS)  g_numTestPoints = MAX_TEST_POINTS;
    if (g_numTestPoints < 4)  g_numTestPoints = 4;
    ptrToPoints = testPointsXY;
    for (i = (g_numTestPoints * NUM_DIMENSIONS); i> 0; i--) {
        *ptrToPoints++ = ((rand() % MAX_RAND) - xyOffset) * scaleFactor;
    }

    for (int i = 0; i < g_numTestPoints* NUM_DIMENSIONS; i++)
    {
        R3 pt;
        pt.c = testPointsXY[i];
        pt.r = testPointsXY[(i*3)+1];
        pt.z = testPointsXY[(i*3)+2];

        pts.push_back(pt);
    }

    std::vector<Tri> tris;
    //
    int ts = NewtonApple_Delaunay(pts, tris);

    // put those random points into a buffer for display
    ptrV = testvertexes;
    ptrToPoints = testPointsXY;

    for (i = 0; i < 30; i++) {
        // scale to between -1 and +1 since that all that this tutorial program was designed to show
        ptrV->Pos.x = pts[i].r;
        ptrV->Pos.y = pts[i].c;
        if (NUM_DIMENSIONS == 3)  ptrV->Pos.z = pts[i].z;
        else   ptrV->Pos.z = 0;
        // give the nodes different colors to make it easier to distinguish between the triangles, especially when they are filled
        brightness = (float)i / (float)30;
        ptrV->Color.x = brightness;
        ptrV->Color.y = brightness * 0.2f;
        ptrV->Color.z = brightness * 0.6f;

        ptrV->Color.w = 1.f;
        ptrV++;
    }

    std::vector<WORD> triangeList;

    triangeList.resize(tris.size() * 3);

    for (int i = 0; i < tris.size(); i++)
    {
        triangeList[i*3] = tris[i].a;
        triangeList[(i*3)+1] = tris[i].b;
        triangeList[(i*3)+2] = tris[i].c;

    }
    std::vector<WORD> lineIndex;

    lineIndex.resize(tris.size()*3*sizeof(WORD));
    int  l, t;
    for (l = 0, t = 0; t<tris.size()*3; t += 3) {
        // Each triangle has 3 lines, so D3D_PRIMITIVE_TOPOLOGY_LINELIST needs 6 vertices
        // Each vertex has to be listed twice
        lineIndex[l] = triangeList[t];      l++;
        lineIndex[l] = triangeList[t + 1];    l++;
        lineIndex[l] = triangeList[t + 1];    l++;
        lineIndex[l] = triangeList[t + 2];    l++;
        lineIndex[l] = triangeList[t + 2];    l++;
        lineIndex[l] = triangeList[t];      l++;
    }
    ReleaseD3D_Buffers();   // from the previous cycle

                            // Fill in a buffer description for the triangle vertices
    D3D11_BUFFER_DESC bd;
    ZeroMemory(&bd, sizeof(bd));
    bd.Usage = D3D11_USAGE_DEFAULT;
    bd.ByteWidth = sizeof(SimpleVertex) * g_numTestPoints;
    bd.BindFlags = D3D11_BIND_VERTEX_BUFFER;
    // Fill in the subresource data
    D3D11_SUBRESOURCE_DATA InitData;
    ZeroMemory(&InitData, sizeof(InitData));
    InitData.pSysMem = testvertexes;
    pd3dDevice->CreateBuffer(&bd, &InitData, &g_pTestVector);

    // Fill in a buffer description for filled triangles
    ZeroMemory(&bd, sizeof(bd));
    bd.Usage = D3D11_USAGE_DEFAULT;
    bd.ByteWidth = tris.size()*sizeof(WORD); // <---- numTriangleVertices comes from the function
    bd.BindFlags = D3D11_BIND_INDEX_BUFFER;
    bd.CPUAccessFlags = 0;
    ZeroMemory(&InitData, sizeof(InitData));
    InitData.pSysMem = static_cast<void *>(triangeList.data());      // <---- triangleIndexList is from the function also
    pd3dDevice->CreateBuffer(&bd, &InitData, &g_pTestVectorIndexBuffer);

    // Fill in a buffer description for drawing only the triangle outlines
    ZeroMemory(&bd, sizeof(bd));
    bd.Usage = D3D11_USAGE_DEFAULT;
    bd.ByteWidth = lineIndex.size();   // <---- from the function
    bd.BindFlags = D3D11_BIND_INDEX_BUFFER;
    bd.CPUAccessFlags = 0;
    ZeroMemory(&InitData, sizeof(InitData));
    InitData.pSysMem = static_cast<void *>(lineIndex.data());
    pd3dDevice->CreateBuffer(&bd, &InitData, &g_pTriOutlineIndexBuffer);

}

```

# Answer
Please debug your code to detect where is the error. Then if you still doesn't figure it out what could be wrong, come to SO with a more detailed report than the actual about your problem in specific.
> -1 votes

---
Tags: directx11
---


# Question
Title: Precalculate/Validate auto battle game outcome on client/server?
All those idle/clicker hero games out there made me wonder how the server usually verifies the games where the player has no influence at all. I'm sure both clients would return the same result if no hacking found place but surely the server checks if both games where legit.

For anyone who don't know the games. You pick X heroes for your defending team and enlist yourself for PvP. These heroes have countless of levels, abilities and equipment. Now anyone who has a defensive team can attack other players defense. This battle will be played out in front of the player and in most games cannot be influenced at all. Another important factor is that the defending player does not have to be online and can watch it later.

Now the question is how can I have the exact same outcome of a battle on server and clients. I don't think I should bother with checking each move against the server and predicting other entities on the client but using random to precalculate the result on the server and can be used to play/replay on the clients too.

Afaik, a basic (not so random) random number generator would generate the same numbers in sequence on different devices. I am using java and a quick search gives the following:

*"If two instances of Random are created with the same seed, and the same sequence of method calls is made for each, they will generate and return identical sequences of numbers. In order to guarantee this property, particular algorithms are specified for the class Random. Java implementations must use all the algorithms shown here for the class Random, for the sake of absolute portability of Java code. However, subclasses of class Random are permitted to use other algorithms, so long as they adhere to the general contracts for all the methods."*

So with that theory I could have a identical battle model for both clients and server. When a battle commences the server generates a seed and if both clients and the server use the same seed they should see the same outcome.

So the issue is getting all the methods run in the exact same order. So I need the game to run exactly the same on both devices regardless of speed and hickups. How would I do this?

* Making the game framerate independent would caus issues since then I need to interpolate a lot when there is a hickup on a device. And even then I can imagine a unit having a slightly different position which can cause a snowball effect.
* Making the game framerate dependent would solve this, both games now need an equal amount of frames/steps. But this can make the game feel "jaggy" if there are just some slight deviations in framerate.
* Other ideas?

Now the server is different. Obviously I do not need to simulate the entire battle to show it to anyone, I just need a win or a loss and perhaps some stats from the battle like damage done. If it's possible I just want to fetch the result and slam that straight into the database even before the players are past the battle loading screen. If I make the game framerate dependent, so it's just about steps, I could just loop trough the whole game on the server.

I know it's a somewhat broad question but I'm sure there is a good answer for the question stated in the title. Afterwards I can clean up my question.

# Answer
> -1 votes
I think I found an answer for my question. While searching for deterministic behaviour I came across implementing replay functionality. It's like I explained in the answer and deterministic was the word I'm looking for. It basically guarantees the same outcome because the steps will be the same on every machine. On the server it runs in a continues loop the game client needs to make sure it runs in a fixed time step.

-edit- So as far as I understand now, to make a game deterministic everything should happen in the exact same order and in the exact same manner on each run/machine/device. A game loop simply tackles the first already, unless you randomly start calling methods with reflection. Also, if you use a deterministic `Random()` function you should seed it in the same way of every run obviously. And the starting state of the game should be exactly the same.

Now as for the manner in how functions behave they can defer if you are passing and using a delta time to it. Here is an example:

```
// normal frame (0.016s)
velocity.x * delta; //(0.016s)
// laggy frame (0.054s)
velocity.x * delta; //(0.054s)

```

Even the slightest deviation in frame time can result in completely different behavior after just a couple of frames. A deterministic physics engine will time step already under the hood. There is a really easy way to fix this, all we need to do is pass in the exact same delta each frame and we are done. A fixed number like `0.016` for a 60fps game should do the trick already really well. But what if the device is severally lagging and going down to 10fps for a while? Then we see our game slow down 6 times, it's like we put in raw numbers for velocity and position without multiplying by the delta time. A simply fix would be to to have it run the update with the fixed delta 6 times. This of course still results in choppy visuals but at least the games speed will remain as intended.

Conclusion, if you do not need delta time then you most probably already have a deterministic game. Obviously you need the same seed if you use random and there should not be any black magic into how you call your functions. In that regard most games are already deterministic.

Now on to some code. I want to credit the first article I found about creating replay functionality. Essentially my question is about this, I just did not realize it. All I need to do is run the simulation on the server to determine the win. Then whenever the client wants to watch it it should play exactly the same, as in a replay. The article goes in depth on the pro's and cons of deterministic replay functionality. The code that got me started is almost 7 years old but still very up to date. It shows how to do a proper game loop and how to do a fixed time step. I am using LibGDX and thus I already have a game loop, I just need to bend it into a fixed time step.

```
// I am using my BaseScreen class for testing.
// It just sets up a view things like the batch and stage and my assets.
public class FixedStepScreen extends BaseScreen {

    // Calculate how much time between each tick.
    // If a frame takes double this time then 2 ticks will be processed.
    // And thus, this dictates the game speed.
    final double FPS = 60;
    final double STEP_TIME = 1000 / FPS;

    // The maximum amount of updates. If a device lags, it won't try to catch up in a single frame.
    final int MAX_STEPS_PER_FRAME = 4;

    // Time since last update tick.
    double previousTickTime;

    // Object for testing, simple sprite moving from left to right
    Player player;

    public FixedStepScreen(AssetManager assetManager,
                           SpriteBatch stageBatch,
                           GameClient gameClient) {
        super(assetManager, stageBatch, gameClient);

        //Set the tick time to the current time.
        previousTickTime = System.currentTimeMillis();

        player = new Player();
    }

    /**
     * This is the regular game loop in LibGDX. This represents a single frame and logic/draw
     * therefor goes synchronously by default in LibGDX.
     * @param delta
     */
    @Override
    public void render(float delta) {
        super.render(delta);

        // I simulated some very basic lag
        simulateLag();

        double currentTime = System.currentTimeMillis();
        int stepCount = 0;

        double myDelta = currentTime - previousTickTime;

        while ( currentTime - previousTickTime > STEP_TIME &&
                stepCount < MAX_STEPS_PER_FRAME) {

            step();
            // Since we did a tick we should add the tick .
            previousTickTime += STEP_TIME;
            stepCount++;
        }

        System.out.println("Frame took " + myDelta + "ms : " + stepCount + " steps processed this frame.");

        draw();
    }

    /**
     * All deterministic logic should go here. This gets called more often.
     */
    protected void step() {

/*       STEP_TIME is the delta in this case. it is fixed obviously so each step the object will
         move and act based on the same time. Passing this to a none deterministic physics engine
         as the delta will therefor make it deterministic as even a slight variation of time between
         different runs or devices can have huge impact on the calculated physics.*/

        player.step(STEP_TIME);
    }

    // -- I already separated logic(Update) and rendering(draw) in the BaseScreen. --

    /**
     * None deterministic logic, depending on your game this could be a camera, animations or
     * anything you don't need to be deterministic and has no effect on other deterministic elements.
     * @param delta
     */
    @Override
    protected void update(float delta) {
        super.update(delta);

        // If an object has non deterministic it should not use the deterministic step() function
        // for obvious performance reasons.
        player.update(delta);
    }

    /**
     * Just draw normally and let the tick functionality handle the deterministic logic.
     * draw() will be called after all logic from step() and update() is processed.
     */
    @Override
    protected void draw() {
        super.draw();
        spriteBatch.begin();

        player.draw(spriteBatch);

        spriteBatch.end();
    }

    Random random = new Random();

    /**
     * Generates some random lag
     */
    private void simulateLag() {
        if (random.nextInt(100) < 50) {

            double frameLag = STEP_TIME * (random.nextDouble() * 2);

            System.out.println("Artificial lag: " + frameLag + "ms.");

            try {
                Thread.sleep((long)frameLag);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

    }
}

```

Now I do not need to add all the fancy stuff like skipping halfway through the "replay", you can look that up in the first article. All I need to do is create a loop on the server and let the deterministic steps run with the exact same `STEP_TIME` as the client. This will quickly generate an outcome, in my case I can store the all the results I need straight into the database.

Disclaimer: This is still the theory, partly tested and I still need to setup the whole client/server functionality for this. All I can say is "this should work", and we all know here what will happen when you hear that :). I will update.

---
Tags: java, networking, multiplayer
---


# Question
Title: libgdx draw/animate curve (tentacle) according to Box2D spring wavering
The horizontally placed Box2D spring is made of `distantJoint` connected bars, and can bend up and down just like airplane wing does when you flight (bigger amplitude thou).

Ok, the physics part works, but how do I pull on a sprite/texture to have a smooth curve when it bends and waves in box2D?

Even if I compose the picture out of small bars, and spring bends 90 degrees down, there are whitespaces on the top of the spring where it is unclamped and messed up down part where it is compressed. I wasn't able to beat this even for solid color tentacle, but what if there should be a nice picture of an octopus tentacle?

Can you please give a hint how the outer skin e.g. in this game implemented https://youtu.be/nakjRosCeH8?t=10 ? It is waving smooth curve, just like I need. Thanks.

# Answer
I am the developer of Tricone Lab which you linked above.

I guess the first thing to say about the Tricone Lab topology layout implementation (i.e. dynamically adjusting curves) is that it does not use any off-the-shelf physics engine like Box2D. It uses a very specialized library which I wrote myself for dynamically updating 2D planar graphs.

My library uses a data structure which maintains topological relationships. So we have a set of regions, edges and nodes, but we also always know which regions border which edges, etc.

Each edge is made up of a list of vertices but this list can grow or shrink. Each region has a target size (i.e. area). If a region is below target size, then a "force" is applied to the normals of the vertices of the edges bounding the region. Forces are also applied to smooth out edges, to prevent nodes and edges getting to close to each other, and to prevent anything getting too close to the edge of the play area. The combination of different forces on each vertex is summed at each timestep and the vertex is moved according to the balance of forces. An edge acquires a vertex between a pair of its existing vertices which are too far apart (above some threshold). Similarly a vertex is deleted if it is too close to its neighbour.

So that's more or less how the "physics" works. It's probably not something which you would want to apply in another game, unless that game is also about 2D planar graphs.

However something that you might be able to take into your game is the idea that a curved edge has a variable number of vertices which adjusts according to the conditions, so that vertices are added and deleted dynamically to maintain smoothness.

Josh S.
> 1 votes

---
Tags: libgdx, box2d
---


# Question
Title: Determining if a point is perpendicular to a line
I am trying to walk a line that is intersecting a mesh, and given the point on the line I need to see what vertices may be perpendicular to it. My initial idea was to attempt a dot product between the line's direction vector and the direction vector from the point on the line to the mesh's vertex, and then only accept values that were near 0. This resulted in a collection of vertices behind the point on my line. Playing with the threshold values for the dot product check do not seem to help either. Any ideas?

## Code

```
//actual_pos = position of the vertex
//trav_in_soace = point along the line
//m_fireDir = normalized direction vector of the line

Vector3 dir_to_point = actual_pos - trav_in_space;
dir_to_point.Normalize();

float dot_accept = DotProduct(m_fireDir, dir_to_point);
if (dot_accept > max_threshold || dot_accept < min_threshold)
    continue;

```

## Picture with threshold values near 0.5

This is best result I can get and it is still really inaccurate. The orange verts are the points on the purple line, the red and blue are what should be the desired vertices.

# Answer
> 1 votes
Figured out that the dot product math was sound and doing what it was suppose to, but elsewhere I had a space transformation that i didn't need that caused the point on the line to be in a different location. removing that transform fixed my problem.

---
Tags: c++, mathematics, mesh
---


# Question
Title: Up / down powerbar computation at server side
I aplolgize if my question is unclear, because I don't know how to formulate the problem.

I have a player that can do damage with a weapon. The weapon has a min and max damage. Holding the space bar makes a power bar grow and degrow on time, and the hit is fired when the space bar is released. This kind of mechanics is quite everywhere.

I manage to do that in Unity with a scrollbar, using delta time to add or substract some damage on time. However, my game is networked, and I don't want the user to send to the server the damage done, just that the strike is performed and make the server compute the damage done.

Here is a graph to better explain my requirement :

I don't want to do it with add and substract at every delta time at server side because of potential compute costs at many parallel games, and the desync risk. I need a formula or a simple algorithm to get the damage at hit time based on time.

Thanks for any help.

# Answer
> 3 votes
```
int delta = end_time - start_time;
delta = delta % period; // period is the time to repeat the entire pattern
if(delta < time_to_top){
    damage = base + rising_slope * delta;
} else {
    damage = base + falling_slope * (period - delta);
}

```

The key here is the modulo operation (operator %) that will let you grab where in the cycle the attack button was released. Then you can just pretend the player released the button in the first cycle.

# Answer
> 3 votes
You should determine a time based function for damage. Wave functions are well established and allow you to generate a result based on time held without any multi-frame calculations

https://stackoverflow.com/a/1073634

This answer contains several formulas and explanations for common functions. For general use, I recommend changing the function's amplitude to 1.

> **Triangular Wave:**
> `y = abs((x++ % 6) - 3);`
> This gives a triangular wave of period 6, oscillating between 3 and 0.
>
> **Square Wave:**
> `y = (x++ % 6) < 3 ? 3 : 0;`
> This gives a regular square wave of period 6, oscillating between 3 and 0.
>
> **Curvy Triangular Wave:**
> To get a variation of the triangular wave that has curves rather than straight lines, you just need to introduce an exponent into the equation to make it quadratic.
>
> Concave curves (i.e. x^2 shape):
> `y = (x++ % 6) < 3 ? 3 : 0;`
> Concave curves (i.e. sqrt(x) shape)::
> `y = pow(abs((x++ % 6) - 3), 0.5);`

---

Alright, now let's answer your question, I'm going to use a cosine function since it's incredibly simple.

Let's break this down to meet each of your needs.

```
var power = -cos(time_held * period_speed)

```

power will start at -1 and oscillate between -1 and 1 until you let go. The speed of the oscillation is determined by period\_speed.

That's a start, now adjust the range

```
var power = power * 0.5f + 0.5f

```

With this, your power will oscillate between 0 and 1. The value is purely driven by time\_held and does not need to recalculated or compounded every frame.

To get your final output you just do a lerp between min and max.

```
damage = lerp(min_damage,max_damage,power);

```

Once again, this value is calculated purely based on time. All a server needs to know is how long the button was held.

---
Tags: unity, c#, mathematics, algorithm
---


# Question
Title: How do I shade / model low poly smooth surfaces that come to sharp edges?
Consider this model of a tank turret:

The following model has smooth, round surfaces that meet at sharp corners. This is achieved with a high number of subdivisions and marking certain edges as sharp in the software.

But I need to obviously get a low poly model for real time rendering. In the modeling tool I'm using, Blender, I have the option to shade any faces smoothly, but I can't seem to figure out how to get the smooth curved surfaces to come to sharp edges, so maybe I'm not on the right track.

How do I shade / model low poly smooth surfaces that come to sharp edges?

# Answer
You need to set the mesh to smooth, then "cut" the edges that have to be sharp by duplicating them.

You need to select the edges you want to make sharper, then hit Ctrl + E and choose the "edge split" option:

The normals automatically orient themselves:
> 3 votes

---
Tags: models, blender, 3d-modeling
---


# Question
Title: C++ Data structure pattern preferability?
So im looking at ways of handling large amounts of data in situations such as an entity manager or particle system.

So i have concluded to use an object pool, and there are two things that I could do to keep track of the free locations.

I can either have a free list through a linked list or use implement the array as a sorted list.

Both of these methods will work and i am sure there are more. My question is what is the difference and prefered usage cases for each of these methods, and if there is any difference at all.

If u have an questions please ask, and this is a real question and if u find a "duplicate" please check with me first in the comments. Ive had people mark my questions in the past as a duplicate when they were in fact unrelated.

# Answer
The theory will tell that you're likely to get less cache misses (so 'more efficiency' w.r.t. response time) if your objects are close one to another in memory.

This means that if you use an array, *and* your objects are contiguous, *and* you access each of them in a in-memory-sequential fashion, it will be more efficient than if you hop from here to there and here again with a linked list.

That's the theory.

Now, the questions that are left:

* Can *you* get that efficiency?
* Do you *need* that kind of efficiency?

You mentioned an array that you'd keep sorted. Will the time you save by avoiding cache misses be more important than the time it'll take to keep your array sorted?

Did you *profile* your application and realized that you have a bottleneck *there*? It's generally not worth doing premature optimization.
> 2 votes

# Answer
> My question is what is the difference and prefered usage cases for each of these methods, and if there is any difference at all.

Free list is a really good bet if you need stable indices (free list with one big contiguous buffer) or pointers (in which case you use a free list with linked buffers). You do not need to store a stack on the side to reclaim in constant-time.
> 0 votes

---
Tags: c++, algorithm, data-structure, patterns
---


title: Fix my Flow Field pathfinding

text:
# Question
Title: Fix my Flow Field pathfinding
I'm developing prototype of Tower Defense/RTS game and I've implemented simple Flow Field grid. Here is the example (link).

**How to use example:** First click on S50, this will spawn additional units, then wait till all of them clump together, click on SET\_BASE button and click on a free space, this will move the base (red circle) and they'll move to the new location. The problem is that if you click to a relatevely diagonal position, they'll all go straight to the target, while if you give them new order at the same y coordinate, they'll start clumping.

If you click several times to move units around, you'll notice that they're moving pretty well when you order them to move diagonally and clump in a line when going horizontally or vertically.

I ran out of ideas what to do next to fix this, what are yours?

---

A bit more info about my flow field: I do one pass of "Dijkstra distance" and then do second pass of detecting lowest distance neighbor and assign "vector" to that neighbor.

Then, about units movement - every unit every update reads "desired movement vector" from it's current cell, predits its movement, then checks if it will hit the wall, updates movement vector, then checks if it will hit other units and finally updates movement vector.

---

**EDIT:** Here's the source code of movement logic.(link)

And source of flow field generation (link)

I'm sorry for shitty code and stupid comments, it's all "prototyp-ish" as possible.

---

What I want is to achieve less "diagonal-horizontal" difference, because at the current state it's really seem underwhelming and it's unaccetable that you can move all units faster by zig-zagging them to their destination.

# Answer
> 8 votes
> I ran out of ideas what to do next to fix this, what are yours?

Try smoothing the vectors.

# Answer
> 3 votes
I had a similar problem this week, so I thought I'd post what I did. Dijkstra's algorithm is inherently discrete, so it will always give you directions that tend to funnel everyone into the same few cardinal directions.

I would recommend taking a look at Continuum Crowds (Treuille/Cooper/Popovic) and Hybrid Vector Field Pathfinding (Moersch, Hamilton) as a starter. They go over the idea of using cost and potential fields to generate paths to a single source. One key concept is that the potential field satisfies an Eikonal equation at all locations except the goal, and this keeps the potential field smooth.

Once you have a smooth potential field, you can use the gradient to work out which direction to move in at any point.

If you want a bit more of a lighter introduction then take a look at the Froblins (Shopf) presententation from Siggraph 2008 too. One point he mentions in that presentation is that the Fast Marching Method to satisfy the Eikonal equation can be relatively slow due to the need to keep the list of candidate cells sorted (or maintaining a priority queue). An alternative he mentions which I found to be quite a bit faster in my case is the Fast Iterative Method. It's also a bit simpler to implement.

One final thing that's not obvious is that sometimes the quadratic in the Eikonal equation is not solvable. In this case you should drop back to one dimension, as mentioned in another question.

This method is inherently quite expensive to compute I'll warn you! I'm currently calculating paths over a 200 x 200 grid with a 100-step cutoff (so it looks more like a circle), and it takes about 2.23 ms on my 3.4 GHz cpu. This is after some efforts to optimize the obvious things.

Here's an example grabbed from my game showing an overlay of the gradient of the potential field and a path that follows it.

If you have a nice smooth field, one idea I wanted to investigate was that of using the curl of the potential field to send agents on a flanking route for a short while, before returning them back to using the gradient to go directly towards the goal.

---
Tags: path-finding, rts, collision-avoidance
---


# Question
Title: How to make 4 way walking animation in game maker studio 2?
So I am trying to make a 4 way movement for my character, and I cant seem to get the walking animations to work for it. The character moves fine, but whenever he moves, the walking animation doesn't play. I figured it was because I made it so when the button was held down, it put it as the sprite for that direction constantly, so it could never get to the next frame. does anyone know how to bypass this? (btw I am using D&D)

# Answer
Sounds like you need to set the sprite based on a one-time trigger, like a button press or a similar state change. You can use booleans to keep track of the state of your character, and make sure not to trigger animation changes too often that way. Hope this helps.
> 1 votes

---
Tags: game-design, movement, game-maker
---