title: Top-down conveyor belt with Box2D

text:
# Question
Title: Top-down conveyor belt with Box2D
I'm trying to code a conveyor belt for a project made with LibGDX and Box2D and I would like to make it like this one from Bomberman Land Touch.

As you can see, the entities standing on it should be able to go in the opposite direction moving slower, the ones not moving should just be transported towards the direction of the belt, and the ones going along its direction should go faster.

For a single direction belt I first detect when the center of an entity's body is inside the block, and then with `body.applyLinearImpulse(direction)` I move the body. This is working fine because it's applying a lower impulse than the one that the player uses to move and by checking the center of the entity instead of relying on the collide event, when the body is between two belts, it doesn't receive two impulses. This is the outcome:

I see two problems with that: the obvious one is that since it's checking the center of the body, as soon as it's in a belt with a different direction, it instantly changes direction without going to the center of the block. The other one is that while going backwards in a turn, it does a little "jump" due to the previous impulse.

I also tried to replicate the Bomberman mechanism by diving the corners into two fixtures but the result is quite the same (except a bug where the player doesn't move, probably because the center doesn't touch the next half of the block):

How can I mitigate these two problems or how can I rethink the whole structure/mechanism of the block?

**Edit:** I tried to implement the first part of @Theraot answer with this code:

```
if (active) {
        for (Entity e : entities) {
            // Check if the origin of the entity is inside the block
            if (getBody().getFixtureList().get(0).testPoint(e.getOrigin())) {
                // Take the x of the entity center if the inputDirection is horizontal, y otherwise
                float entityAxis = inputDirection.y == 0 ? e.getOrigin().x : e.getOrigin().y;
                // Same for the conveyor block
                float blockAxis = inputDirection.y == 0 ? getOrigin().x : getOrigin().y;
                Vector2 impulse = null;
                // If they are really close
                if (Math.abs(blockAxis - entityAxis) < 0.1f) {
                    impulse = outputDirection;
                }
                else {
                    impulse = inputDirection;
                }
                // Apply the impulse
                e.getBody().applyLinearImpulse(impulse, e.getBody().getWorldCenter(), true);
            }
        }
    }

```

and this is the result.

# Answer
My general suggestion for your whole game mechanic is that you do not want to use the box2d physic forces to implement this. The collision detection might be useful, but low friction objects and impulses is not the right approach to simulate the conveyor belts in my opinion. The physics simulation does not match the reality nicely. But, here are my suggestions, and how they might help with each of your problems.

**Make your avatar collision detectors for the conveyor belts much smaller**

* Your collision detectors are too big. You actually want the fixture that you use to represent the centre of your character avatars to be much smaller, a small dot. I would also make the shape round.
* Then, relative to your tiles, the changes of direction will look close to being in the centre of your tiles.
* You might be trying to overload the fixture that you use for explosion collision detection? Use collision filters to put your conveyors and your player conveyor collision dot in a different group to your avatar bomb hit box and bomb explosions.

**Don't use impulses or box2d forces to to move your characters**

* Forces, impulses and friction are all great in box2d. So good for simulating free physics environments. But your game is not actually like that. It is quite constrained. Only x,y axis movement, from controller or conveyor. And movement only happens on what you want to be a grid of lines. There is not free movement to wobble around inside a tile, or there should not be.
* Rather use the collision events to register that one or many conveyor belts are acting on your avatar (You can have multiple during a transition from one to the other). Begin collision to register and deregister on end collision.
* Treat controller/player input in a similar way. Right arrow down register +1 for x-axis.
* During a step in your game loop, do your rudimentary physics. Look at forces wanting to be caused by any controller input or conveyor belts that are touching each avatar, do some math and move your character.

**Transitions from one conveyor to another should be handled deterministically**

* Probably a few options here, but in your game loop you need choose which conveyor to listen to, and this is where we can use precise points.
* Pick a point that is maybe just inside the edge of the end of each conveyor belt, but still in its centre axis.
* Select the belt end that your avatar is closest to.

I think you might still experience some drift if you go around a loop of belts for long enough, but you can make any movement also make an interpolated correction to be on the closest valid x or y coordinate depending on if you are moving vertically or horizontally.
> 1 votes

# Answer
They are not composite of two triangular belts.

I will be taking as example the bottom right corner in your loop. However, to keep this general, I need a bit of nomenclature...

Let us say that the belt corner has an input side and an output side. These are always on different axis of each other. So, each belt corner has an input axis and an output axis.

In the example, the input side is the top and the output side is the left. Then the input axis is vertical and the output axis is horizontal. Makes sense?

Now, what you will do:

* check if the object is on top of it, if it isn't do nothing.
* check if the object position on the input axis is before the center of the belt corner, if it is move the object along the input axis...
* if it isn't, move the object along the output axis.

I would use an special tile... However, since we are checking along the input axis, I suppose you could creat this from two belts dividing the tile. In the example, they would be one rectangular half tile on the top and one on the bottom. However, you would have to fix the visuals. Also, fix the problem of the center being between the tiles (here the output tile should have preference).

This should move the object down to the vertical position of the center to corner and then to the new direction. However, if the object did enter from below or from the left, it won't move down. And if it did enter from the right, it may or may not move down depending on the vertical position of the object.

*I have not implemented this over a physics engine, although I do not expect it to be any harder.*

---

**Addendum**:

After having a look at your code and the result you got...

1. To reiterate. Input and output, side and axis, are of the corner tile. They define its orientation, and are independent of the object that is being carried by it. For example, the bottom right corner of your loop has vertical (from the top) input and horizontal (to the left) output.
2. You do not check if the coordinate of the object and the belt are close (they are, you checked the object is on the belt), check if the entity is on the first part of the tile.

Ok, I understand that is confusing, however, with your code I can make an approximation of how to do it in your tool set...

Since you are using the direction for the impulse, I am assuming that you are representing the directions like this:

```
INPUT

Top    (going down)  = {x: 0, y: 1}
Bottom (going up)    = {x: 0, y:-1}
Left   (going right) = {x: 1, y: 0}
Right  (going left)  = {x:-1, y: 0}

OUTPUT

Top    (going up)    = {x: 0, y:-1}
Bottom (going down)  = {x: 0, y: 1}
Left   (going left)  = {x:-1, y: 0}
Right  (going right) = {x: 1, y: 0}

```

I am also assuming that the origin is the center.

Then:

```
bool horizontal = inputDirection.y == 0;
float blockAxis = 0;
float side = 0;
if (horizontal)
{
    entityAxis = e.getOrigin().x;
    side = inputDirection.x;
}
else
{
    entityAxis = e.getOrigin().y;
    side = inputDirection.y;
}

// ...

for (Entity e : entities) {
    if (getBody().getFixtureList().get(0).testPoint(e.getOrigin())) {
        float entityAxis = horizontal ? getOrigin().x : getOrigin().y;
        // If the entity is on the input side
        // (same sign check)
        if (((blockAxis - entityAxis) * side) > 0) {
            impulse = inputDirection;
        }
        else {
            impulse = outputDirection;
        }
        // Apply the impulse
        e.getBody().applyLinearImpulse(impulse, e.getBody().getWorldCenter(), true);
    }
}

```

**Notes**:

1. Given the graphics, perhaps you want to use an invisible entity for the collision box of the avatar, placed around its feet, and use it for all checks. Then place the visible entity that holds the srpites of the avatar relative to it.
2. You might be interested in a way to get only nearby entities. In particular if you will be working with large maps or large quantities of entities.
> 0 votes

---
Tags: 2d, libgdx, physics, box2d
---


# Question
Title: How can I make my mouse rotate my character?
I have third person view on my character already, but I can't figure out how to make my camera rotate my player using Unity.

# Answer
I assume that you know about Layer Masks so I'm going to jump directly to the piece of code and explanation:

So I created a parent project which holds the script called "PlayerController" and the capsule model.Then we have two children: Cube is the red one that I have added just to see the change of the direction of the Player. Player plane is actually responsible to check the raycast that we will cast to see the difference between the mouse position and the player position, let's see how :

```
private RaycastHit _hit;

private void Update()
{
    var mousePosition = Input.mousePosition;
    var cameraRay = Camera.main.ScreenPointToRay(mousePosition);
    var layerMask = LayerMask.GetMask("Ground");

    if (Physics.Raycast(cameraRay, out _hit, 100, layerMask))
    {
        var forward = _hit.point - this.transform.position;
        var rotation = Quaternion.LookRotation(forward);

        this.transform.rotation = new Quaternion(0, rotation.y, 0, rotation.w).normalized;
    }
}

```

Don't forget to add a layer called "Ground" and change the layer of the PlayerPlane object to that new Layer you just created.

I hope this help you.

Happy Coding!
> 0 votes

---
Tags: unity
---


# Question
Title: Unity run-time creating material has performance impact?
Just found creating a material in a script for the first time would have performance impact.
(Using Unity 5.6.5f)

A very simple script for testing is to create a game object with MeshRenderer in Start(), assign a new material each time in Update(),

```
gameObj.GetComponent<MeshRenderer>().material = new Material(Shader.Find("Standard"));

```

From Unity Profiler the first function call took much longer than following calls, the first one took 100ms and others less then 1ms.

Can someone give it an explanation? Thanks.

# Answer
> 0 votes
I'm not sure what kind of explanation you're hoping for here, but the gist is that this is standard "first-time setup" work.

I imagine this only happens in the editor, though I haven't verified that. Unless I'm completely misunderstanding what's being done, the property drawers don't need to be created in a built game. Perhaps try timing there to see if the issue persists.

---

That said, here's some more info if you're curious:

Comparing the first and second frames in the profiler, you can see that the calls under the Material constructor are quite similar. The critical difference comes in `MaterialPropertyHandler.GetHandler()`.

First frame, that method also calls `MaterialPropertyHandler.GetShaderPropertyHandler()`, under which are many other calls, including a fair amount of memory allocation. (231.3KB on my machine).

A quick google search turns up what happens in GetHandler() that makes a difference:

```
if (MaterialPropertyHandler.s_PropertyHandlers.TryGetValue(propertyString, out materialPropertyHandler))
  return materialPropertyHandler;
materialPropertyHandler = MaterialPropertyHandler.GetShaderPropertyHandler(shader, name);

```

I.e., that dictionary (apparently) has to be populated the first time you create a Material. After that, it will skip the call to `GetShaderPropertyHandler()`.

You can adjust when this happens (e.g. in Start() or Awake(), etc.) if you need to, but I don't know of any way to avoid it entirely.

---
Tags: unity, c#, shaders, performance, materials
---


# Question
Title: How to find sequences of consecutive cards of the same suit in a hand, including wild cards? (Indian Rummy)
I have a hand of 13 cards (chosen from 2 standard decks of 52 cards + 4 jokers, so it's possible for the same card to appear multiple times).

I want to search this deck to find sequences according to the rules of Indian Rummy:

* A sequence must contain at least 3 cards, or up to 10 cards

(We need at least two sequences to win / minimize loss penalties, so at least 3 cards in the hand of 13 need to be left over to form another sequence)
* Cards in a sequence have consecutive rank:

2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A (wild cards count as any rank)
* A sequence must be all of the same suit:

♦, ♣, ♠, ♥ (wild cards can count as any suit)
* A sequence is called "pure" if it contains no wild cards standing in for other cards.

eg. if Jacks are wild, the sequence 10♥, J♥, Q♥ is a pure sequence, while the (also valid) sequence 3♣, 4♣, 5♣, J♥, 7♣ is not a pure sequence.

Here's what I've come up with so far, but it does not correctly find all sequences matching the rules above.

```
private List<Card> FindSequences()
{
    List<Card> sequence = new List<Card>();

    int Count = 0;

    //sort in order
    cards = cards.OrderBy (i => i.FaceValue).ToList ();
    sequence.Add(cards[Count]);

    //------------------------------------------------------------------------------------------------------//

    for(int i = 1; i < 9; i++)
    {
        if((cards[i - 1].cardRank == cards[i].cardRank - 1) && (cards[i].cardRank == cards[i + 1].cardRank - 1) && (cards[i + 1].cardRank == cards[i + 2].cardRank - 1) )//&& (cards[i + 2].cardRank == cards[i + 3].cardRank - 1))
        {
            sequence.Add (cards [i - 1]);
            sequence.Add (cards [i]);
            sequence.Add (cards [i + 1]);
        }
        else
        {
            Count++;
            //check If Sequence Less Then 3 Clear Data
            if(sequence.Count < 3)
                sequence.Clear ();
        }
    }

    wildCard.Clear ();
    return sequence;
}

```

# Answer
> -1 votes
var suites = { 'clubs' : \[\], 'diamonds' : \[\], 'hearts' : \[\], 'spades' : \[\], 'stars' : \[\] }; var wilds = \[\]; var buckets = { 3 : \[\], 4 : \[\], 5 : \[\], 6 : \[\], 7 : \[\], 8 : \[\], 9 : \[\], 10 : \[\], 11 : \[\], 12 : \[\], 13 : \[\] }; //can have more then one run/set so these are used to hold valid runs/sets var runs = \[\]; var sets = \[\]; var r\_num = -1; //starts at -1 so ++ will give 0 index var s\_num = -1;

CLUBS, DIAMONDS, HEARTS, SPADES, STARS = range(5) WILD = 0

```
testHand = [(CLUBS,3), WILD, (SPADES,3), (CLUBS,4), (CLUBS,5), (CLUBS,6), (CLUBS,6), (CLUBS,7), (CLUBS,8), (SPADES,10), (HEARTS,10), WILD]

def nextInRun(card):
if card[1] == 13:
    raise ValueError("cannot determine next card in run for %s" % str(card))
    return (card[0],card[1]+1)

        def prevInRun(card):
        if card[1] == 3:
            raise ValueError("cannot determine previous card in run for %s" % str(card))
            return (card[0],card[1]-1)

                def fit2Set(card1, card2):
                return card1 == WILD or card2 == WILD or card1[1] == card2[1]

                    START_RUN, START_SET = range(2)

def removeCard(hand, card, startIdx=None):
hand = copy.deepcopy(hand)
if startIdx != None and hand.index(card) < startIdx:
    startIdx -= 1
    hand.remove(card)
    return ((hand, startIdx) if startIdx != None else hand)

        def startMoves(handr1,card1,startIdx):
        if card1 == WILD:
            #print "trying to start run with 1 WILD card"
            for card2 in set(handr1):
                handr2,startIdx = removeCard(handr1, card2, startIdx)
if card2 == WILD:
    #print "trying to start run with 2 WILD cards"
    for card3 in set(handr2):
        handr3,startIdx = removeCard(handr2, card3, startIdx)
if card3 == WILD:
    yield (START_RUN, 3*[WILD], handr3, startIdx)
else:
    try:
    card2v = prevInRun(card3)
    card1v = prevInRun(card2v)
    yield (START_RUN, [card1,card2,card3], handr3, startIdx)
    except ValueError:
    pass
    else:
        #print "trying to start run with WILD card and %s" % str(card2)
        try:
        card1v = prevInRun(card2)
        card3 = nextInRun(card2)
        #print "card3 = %s, handr2 = %s" % (str(card3),str(handr2))
        canContinueRun = card3 in handr2
        if not canContinueRun and WILD in handr2:
            card3 = WILD
            canContinueRun = True
        if canContinueRun:
            handr3,startIdx = removeCard(handr2, card3, startIdx)
yield (START_RUN, [card1,card2,card3], handr3, startIdx)
except ValueError:
pass
return # no need to start a set with a WILD
    else:
        try:
        card2v = card2 = nextInRun(card1)
        canContinueRun = card2 in handr1
        #print "card2 = %s, handr1 = %s" % (str(card2),str(handr1))
        if not canContinueRun and WILD in handr1:
            card2v = card2
            card2 = WILD
            canContinueRun = True
        if canContinueRun:
            handr2,startIdx = removeCard(handr1, card2, startIdx)
card3 = nextInRun(card2v)
canContinueRun = card3 in handr2
#print "card3 = %s, handr2 = %s" % (str(card3),str(handr2))
if not canContinueRun and WILD in handr2:
    card3 = WILD
    canContinueRun = True
if canContinueRun:
    handr3,startIdx = removeCard(handr2, card3, startIdx)
yield (START_RUN, [card1,card2,card3], handr3, startIdx)
except ValueError:
pass
handrs = copy.deepcopy(handr1)
for card2 in set(handr1):
    handrs.remove(card2)
    if not fit2Set(card1,card2):
        continue
        handr2,startIdx = removeCard(handr1, card2, startIdx)
for card3 in set(handrs):
    if not fit2Set(card1,card3):
        continue
        handr3,startIdx = removeCard(handr2, card3, startIdx)
yield (START_SET, [card1,card2,card3], handr3, startIdx)

def startings(hand,startIdx=0,runs=[],sets=[]):
#print "get startings for\n hand = %s\n startIdx = %d\n runs = %s\n sets = %s" % (str(hand),startIdx,str(runs),str(sets))
if len(hand) == 0 or startIdx >= len(hand):
    yield copy.deepcopy(hand),copy.deepcopy(runs),copy.deepcopy(sets)
return
    card = hand[startIdx]
        while hand.index(card) < startIdx:
            startIdx += 1 # do not try to start with the same card twice here
                if startIdx >= len(hand):
                    yield copy.deepcopy(hand),copy.deepcopy(runs),copy.deepcopy(sets)
        return
            card = hand[startIdx]
                #print " actual startIdx = %d" % startIdx
                handr = removeCard(hand, card)
                for move in startMoves(handr, card, startIdx):
                    if move[0] == START_RUN:
                        runs2 = copy.deepcopy(runs)
                        runs2.append(move[1])
                        for starting in startings(move[2], move[3], runs2, sets):
                            yield starting
                            elif move[0] == START_SET:
                            sets2 = copy.deepcopy(sets)
                            sets2.append(move[1])
                            for starting in startings(move[2], move[3], runs, sets2):
                                yield starting
                                for h,r,s in startings(hand, startIdx+1, runs, sets):
                yield h,r,s

                def runExtensions(run,handSet):
                if set(run) == set([WILD]): # run consists only of WILD cards
                    for card in handSet:
                        yield card
                else:
                    runUnique = list(set(run))
                        cardv = runUnique[0] if runUnique[0] != WILD else runUnique[1]
                            idx = run.index(cardv)
                            lastCardVal = cardv
                            while idx < len(run)-1:
                                lastCardVal = nextInRun(lastCardVal)
                                idx += 1
                                try:
                                nextCardVal = nextInRun(lastCardVal)
                                if nextCardVal in handSet:
                                    yield nextCardVal
                                    return
                                        if WILD in handSet:
                                            yield WILD
                                            except ValueError:
                                            pass

                                            def fillings(hand, runs, sets):
                                        if len(runs) > 0:
                                            run1 = runs[0]
                                            noExtensionFound = True
                                            usedWildExtension = False
                                            for runExtension in runExtensions(run1,set(hand)):
                                                noExtensionFound = False
                                                run1e = copy.deepcopy(run1)
                                                run1e.append(runExtension)
                                                handr = removeCard(hand, runExtension)
                                                runse = [run1e] + copy.deepcopy(runs[1:])
                                                for filling in fillings(handr, runse, sets):
                                                    yield filling
                                                    if runExtension == WILD:
                                                        usedWildExtension = True
                                                        # when extending with WILD: also try without extending the first run; WILD card could be needed in another run
                                                    if noExtensionFound or usedWildExtension and len(runs) > 1:
                                                        for h,r,s in fillings(hand, copy.deepcopy(runs[1:]), sets):
                        r = [run1] + r
                        yield h,r,s
                return
                    handr = copy.deepcopy(hand)
                        setse = copy.deepcopy(sets)
                        for card in hand:
                            for set_i in setse:
                                if fit2Set(card, set_i[0]):
                                    handr.remove(card)
                                    set_i.append(card)
                                    break
                                    yield handr,[],setse

                        def valueCard(card):
                        if card == WILD:
                            return 20
                                return card[1]

                                    def value(hand):
                                    return sum([valueCard(card) for card in hand])

                                        def strRepSuit(suit):
                                        if suit == CLUBS:
                                            return 'clubs'
                                                if suit == DIAMONDS:
                                                    return 'diamonds'
                                                        if suit == HEARTS:
                                                            return 'hearts'
                                                                if suit == SPADES:
                                                                    return 'spades'
                                                                        if suit == STARS:
                                                                            return 'stars'

                                                                                def strRepCard(card):
                                                                                if card == WILD:
                                                                                return 'WILD'
                                                                                return '%s%d' % (strRepSuit(card[0]), card[1])

                                                                                def strRepCardSuit(card):
                                                                                if card == WILD:
                                                                                return 'WILD'
                                                                                return strRepSuit(card[0])

                                                                                def strRepVal(card):
                                                                                if card == WILD:
                                                                                return 'WILD'
                                                                                return '%d' % card[1]

                                                                                def strRepRun(run):
                                                                                setRun = set(run)
                                                                                if setRun == set([WILD]):
                                                                                return '%d * %s' % (len(run),strRepCard(run[0]))
                                                                                runUnique = list(setRun)
                                                                                suit = (runUnique[0] if runUnique[0] != WILD else runUnique[1])[0]
                                                                                return '%s %s' % (strRepSuit(suit), ','.join([strRepVal(card) for card in run]))

                                                                                def strRepSet(set_):
                                                                                setUnique = list(set(set_))
                                                                                val = (setUnique[0] if setUnique[0] != WILD else setUnique[1])[1]
                                                                                return '%d %s' % (val, ','.join([strRepCardSuit(card) for card in set_]))

                                                                                def strRepSol(hand,runs,sets):
                                                                                return ' runs: %s\n sets: %s\n hand: %s\n hand value: %d' % ('; '.join([strRepRun(run) for run in runs]), '; '.join([strRepSet(set_) for set_ in sets]), ','.join([strRepCard(card) for card in hand]), value(hand))

                                                                                def optimizeHand(hand):
                                                                                lowestHandValue = value(hand)
                                                                                bestSolution = hand,[],[]
                                                                                for handr,runs,sets in startings(hand):
                                                                                #print "starting with\n runs = %s\n sets = %s\n handr = %s" % (str(runs),str(sets),str(handr))
                                                                                if len(runs) == 0 and len(sets) == 0:
                                                                                continue
                                                                                if len(handr) == 0:
                                                                                print "solution generated without filling"
                                                                                lowestHandValue = 0
                                                                                bestSolution = [],runs,sets
                                                                                break
                                                                                for solution in fillings(handr,runs,sets):
                                                                                handValue = value(solution[0])
                                                                                if handValue < lowestHandValue:
                                                                                lowestHandValue = handValue
                                                                                bestSolution = solution
                                                                                print "solution improved:\n%s" % strRepSol(bestSolution[0], bestSolution[1], bestSolution[2])
                                                                                if lowestHandValue == 0:
                                                                                break
                                                                                if lowestHandValue == 0:
                                                                                break
                                                                                print "best solution:\n%s" % strRepSol(bestSolution[0], bestSolution[1], bestSolution[2])
                                                                                #return lowestHandValue, bestSolution

```

---
Tags: unity, algorithm, card-game
---


# Question
Title: How can I select an enemy to act next, biased toward smaller enemies?
Suppose there are X number of enemies in the game. They all have to attack one by one. Each enemy is picked randomly, and can be of Y size.

How can we attain biased randomness in such a way that small enemies are attacking more often than big ones?

My current algorithm is "pick any random enemy" no matter the size, and I'd like to improve on this.

# Answer
Try accounting for larger enemies multiple times, then drawing one from them. For instance let's say you have 6 enemies, two of them are medium, one is large and the other 3 are small. Then you'd have a list similar to

```
small A, small B, small C, medium A, medium A, medium B, medium B, large A, large A, large A

```

If you pick one of these random, then you'll obviously have a larger chance to pick large A, than small a
> 6 votes

# Answer
Let's say the size-values are as follows:

```
small  = 3;
medium = 2;
large  = 1;

```

In this situation, you could add all size-values of your enemies together to calculate a biased random. For Example:

```
smallUnitsTotal  = 4; // => 12 points total (4 * 3)
mediumUnitsTotal = 2; // =>  4 points total (2 * 2)
largeUnitsTotal  = 1; // =>  1 points total (1 * 1)
totalPoints = (12 + 4 + 1)= 17 points total

```

Now you can just pick a random number (r) between 1 and 17. If r \<= 12, a random small enemy attacks. If r \> 12 && \<= 16, a medium unit attacks and otherwise, the large unit attacks.

Hopefully this helps!
> 2 votes

# Answer
I'd be tempted to handle it like a raffle. Every time an attack slot comes around, everyone gets a number of raffle tickets according to their attack frequency. Then you do a random draw from those tickets, and deduct tickets from the winner. Everyone else keeps their tickets for the next draw, so someone who hasn't been picked in a while will gradually become more likely to get their turn.

```
Enemy SelectAttacker(List<Enemy> enemies) {
    float totalWeight = 0f;
    float weightAdded = 0f;
    float greatest = float.negativeInfinity;

    // Hand out raffle tickets to everyone in line to attack.
    foreach(var enemy in enemies) {
        // GetAttackRate can change value depending on the character's state,
        // like returning 0 if stunned / out of range, or a boosted value if enraged.
        float weight = enemy.GetAttackRate();

        weightAdded += weight;
        enemy.accumulatedAttackWeight += weight;
        greatest = Max(greatest, enemy.accumulatedAttackWeight);

        totalWeight += Max(enemy.accumulatedAttackWeight, 0f);
    }

    // Contingency: if the enemies who were holding all the raffle tickets died,
    // and everyone remaining is in attack debt, fast-forward a few rounds' worth.
    if(greatest <= 0f) {
        float advance = (Floor(-greatest / weightAdded) + 1) * weightAdded;
        totalWeight = 0f;
        foreach(var enemy in enemies) {
            enemy.accumulatedAttackWeight += advance;
            totalWeight += Max(enemy.accumulatedAttackWeight, 0f);
        }
    }

    // Choose a winner.
    float random = Random() * totalWeight;
    totalWeight = 0f;
    foreach(var enemy in enemies) {
        totalWeight += Max(enemy.accumulatedAttackWeight, 0f);
        if(totalWeight > random) {
            // Penalize this enemy proportionate to the crowd still waiting.
            // This keeps the total number of tickets in circulation controlled.
            enemy.accumulatedAttackWeight -= weightAdded;
            return enemy;
        }
    }

    // Fallback, only hit in the event of invalid input
    // (like NaNs / negative attack rates)
    return enemies[0];
}

```

A few neat things about this approach:

* Enemies can have fractional attack weights (in case this enemy really needs to attack 2.3 times as often as that other one), without blowing up all your weights to multiples of a common divisor.

All of these weights are relative, so two enemies with `GetAttackRate` returning 3 will (on average) attack as often as each other, three times as often as an enemy with `GetAttackRate` returning 1, and half as often as an enemy with `GetAttackRate` returning 6, no matter the composition of the battle group.
* This method scales linearly to any number of enemies, and the overhead remains constant no matter how disparate your weights (compared to drawing cards from a deck, where an enemy that attacks 10 times as often as another needs 10x the storage in the deck)
* You can easily vary the attack selection priorities dynamically based on enemy states or other factors. We don't need to do much grooming of the selection data as enemies join, change state, or die.
* Enemies that have attacked a lot recently tend to go into an "attack debt" with negative tickets held, limiting runs of the same enemy being chosen.
> 1 votes

# Answer
This can be handled by a straight forward reverse weighting.

Assign enemy size 'Y' as a numeric value (ex. 1-4). Choose a ceiling value 'Z' that is greater than the largest possible value of 'Y' (The greater the difference between 'Z' and the highest 'Y' value will result in the least difference in attack frequency)

Provide each enemy with a weighting value of 'Z' - 'Y'.

Create a list of enemies with each having a number of entries equal to their weighting value.

Calulate the sum of all all weighting values and generate a random number between 1 and the sum.

Use this to pick an index from the list and that is the monster that attacks this turn.

There are numerous optimisations that can be applied to this, but this will give the functionality you have requested.
> 1 votes

# Answer
What I did was a straight-forward algorithm for biased randomness or weighted probability.

Getting sum of weights.Weight is nothing but the prioririty given to an object.In my case the smaller the enemy the bigger the weight.

```
for(int i=0; i < value.size; i++) {
  weight_size = weight_size + value.get(i).getInt("weight");
}

```

Getting random weight from 0 to total weight.

```
double random_weight = Math.random() * weight_size;

```

Calculating which to choose based on weight.Loop on the objects until random weight is less than the weight of the object.

```
    for(int i=0; i < value.size; i++) {
        if (random_weight< value.get(i).getInt("weight")) {
            return value.get(i);
        }
        random_weight -= value.get(i).getInt("weight");
    }

```

**Simple yet effective.**
> 0 votes

---
Tags: game-design, algorithm, probability
---


# Question
Title: In Unity, how do get access to animation clips in selected model from EditorWindow?
I need to add some animation events or copy them from other models. So I decided to make a EditorWindow. Unfortunately there's not much information about this, and I'm stuck in here.

```
void OnGUI() {
    GUILayout.Label("Source Object contains Animation Clips", EditorStyles.boldLabel);
    sourceObject = (GameObject) EditorGUILayout.ObjectField(sourceObject, typeof(Object), false);

    if(GUILayout.Button("Copy")) {
        if(sourceObject == null) {
            throw new System.NullReferenceException("Source Object is missing.");
        }

        // Do Copy here

    }
}

```

What I need to do is:

1. Extract all animation clips from the selected model(fbx) - it's the source object
2. Select "AnimationClip" to want to copy. Note that AnimationClip in here is not inside of model, it's seperated AnimationClip that duplicated from original model because basically animation clip from imported model is read-only, so I have to duplicate to update it.

How do I get animation clips from selected fbx model with ObjectField? Any advice will very appreciate it.

# Answer
I solved this by getting Animation Clip directly as input, not GameObject.

```
sourceClip = (AnimationClip) EditorGUILayout.ObjectField(sourceClip, typeof(AnimationClip), false);

```

Now I can access any information about AnimationEvents, Curves and others.
> 0 votes

---
Tags: unity, animation, editors
---


title: Vector normalize in Unity

text:
# Question
Title: Vector normalize in Unity
I was watching a tutorial about Vectors in Unity, I understood the meaning of normalizing a vector but **I wanna know why do we normalize a vector and if we don't what will happen ?**

# Answer
> 2 votes
There are reasons someone might want to normalise a Vector, including dealing with directions. Normals on meshes, for example, are normalised, because you only care about their direction, not their length.

It also makes the math work, because if you have multiple normal vectors with different lengths, it would be impossible to calculate values (like lighting) in a uniform way.

# Answer
> 1 votes
There are operations that do not make sense when the vector is not normalized. Some examples:

1. When you want to get the projection of a vector on another vector. You want to normalize the second one so that you only get its direction.
2. When you are dealing with basis vectors in a Cartesian coordinate system. This is where matrix transformations and viewing in 3D space comes into play.

There are a lot more, but this is the gist of it.

---
Tags: unity, mathematics
---


# Question
Title: Efficiently determining which buildings are connected by roads
I have a question about the most effective way to detect road connection in a tile based world. Some time ago I already asked for "How to improve performance for expensive functions in 2d city builder" which was about building radius. Those hints were quite useful and worked great. But now in this case I don't see I could use the same way as mentioned in that post. Let's start with my problem by a first image:

You can see 5 buildings on this little map. One on the left/the beginning of the map and four at the end of the long road on the right. All road tiles (separated in the black squares) are connected with each other.

Since I have to check if a building is still connected to the building on the left (which is the city entrance) it's needed to do regular road checks. To avoid doing expensive pathfinding stuff for each building I store the connection information in each road tile to have faster access. In the next image you can see those information. All road tiles have the same information since they are all connected to each other):

That works quite fast in smaller maps but if the map gets bigger, it's getting more expensive. My proceeding is the following: if a building is placed on a map it looks for surrounding roads. For these roads (could be up to 4 - for each direction) I check on and on if the next tile also has surrounding roads and so on. So finally I get an array of road tiles and update the road object information in all of them (whether building has been placed or removed). Do you know any optimization for this procedure already?

Since in a larger map I get an even bigger problem with the following situation:

Now I have a lot of objects on the right part of the map (this can be much, much bigger of course with hundreds of roads and buildings). If the player now disconnects the long road next to the building on the left, a lot of roads need to be updated.

Do you have any idea how I could improve handling this situation?

# Answer
> 1 votes
I'd be tempted to approach this with a Disjoint Set data structure.

This can efficiently answer "are these two items in the same connected set?" (to see if two buildings are connected by roads, for instance) and join two connected sets (like when a new road bridges a gap).

Detecting when a connected set gets disconnected is a bit more involved, but we can use the features of the data structure to cut down on redundant work.

The basic idea is that each element of the set (ie. each road tile) refers to a "parent" element. You can do this with a pointer, or an index/ID, and it can be stored either in the road itself or a parallel array.

To check which connected set an element is in, we follow these references up to the root of the set they're in (a road whose parent is itself):

```
Road FindRoot(Road road) {
    if( road.parent == road)
        return road;

    return FindRoot(road.parent);
}

```

(This can be optimized with path compression / splitting / halving, where we update these parent references during the lookup process, so future lookups have fewer hops)

We can then check if two items are in the same connected set by checking if they're under the same root:

```
bool IsConnected(Road a, Road b) {
    return FindRoot(a) == FindRoot(b);
}

```

So instead of maintaining lists of connected buildings to search through, you can instead check if a road adjacent to your source building and a road adjacent to your destination building are connected. Using the optimizations mentioned above, this becomes a constant-time operation when queried repeatedly.

To build these connected sets, we initialize a road's `parent` to point to itself. Then, each time two road tiles meet (as when parsing a map on load, or online as the player places new roads), we use the Union function:

```
void Union(Road a, Road b) {
    Road rootA = FindRoot(a);
    Road rootB = FindRoot(b);

    if(rootA == rootB)
       return; // Already in the same connected set.

    // Join sets under a common root.
    rootB.parent = rootA;
}

```

(Again, there are optimizations we can apply called Union by Rank or by Size, which help us get flatter trees for faster queries.)

It might look like a lot of pointer-chasing, but if you use the optimizations described in the linked articles then this structure is blazingly fast, with union & find operations taking nearly constant time on average.

When a road tile is removed, we might need to split a group into multiple parts, or fix up `parent` references that were referencing the removed road. But we can do this in time linear in the number of roads in the connected set:

Clear the `parent` reference of each road adjacent to the new gap.

Then, run a depth-first search along the road network, using the first of these stubs as a starting point. For each road encountered along the way (including the starting point), set that road's `parent` to the starting point.

Next, inspect the next road stub bordering the gap. If its parent reference has been set, then it's already connected to the other side via some other route and we don't need to search it again. Otherwise, repeat the search, setting roads in this connected component to have *this* stub as their `parent`.

Repeat until all road tiles bordering the removed tile have been updated in this way, and we're back to a valid disjoint set data structure.

# Answer
> 1 votes
You should be using some form of Graph structure. Instead of every road storing information for every other road connected, it should only store the roads that directly connect to it. Or a better way would be to store only the junctions (nodes) and which other junctions connect to it (a dead end should count as a "junction", as should corners), as well as the number of tiles (or cost if you have different road types) between them.

This will give you a graph you can pathfind on. You can then use Dijkstra's algorithm to find the shortest distance back to the start for all nodes; any which have not had a distance set at the end are unconnected.

Buildings and/or individual road tiles should store the nearest junction to them that they are connected to. Then, knowing which junctions are not connected, any of the buildings that are closest to those junctions can be flagged as not being connected.

The main thing to do would be keeping the graph up to date. For adding tiles, this is simple; when a new junction or connection is made, check and add any distances, and then update distances produced by the Dijkstra's algorithm if they are less than the current distance.

When removing roads, flag the Dijkstra's algorithm to recalculate (probably after, say, X seconds after the last delete, in case they are doing large scale remodeling).

Another advantage of having a graph for the roads is you can run A\* on it if you want things like cars.

---
Tags: monogame, performance, path-finding, tilemap, city-builder
---


# Question
Title: How can I store in-game money so that nobody can manipulate the amount?
People get coins for completed tasks(for example completing a level) in my game. In addition, they can purchase coins(they need to pay for that with real money) in the app store. With these coins, people can purchase different items in the game.

Is it easy for somebody to manipulate the amount of coins when I store it as an integer variable in a text file on the device(iOS and Android phones and tablets)?

What is the best way in MonoGame/Xamarin to store the amount of coins so that nobody can manipulate it afterwards?

# Answer
The only solution would be to have a validation server; that being said, you mentioned not wanting them to always have an internet connection and that being one of the reasons you did not want to implement this solution but I would like to remind you that to buy things on the app store the user will need to have an internet connection at that moment.

Because of that required connection, you dont need to have Always-OnLine checks if you use a "real-money" economy and a "game world" economy. You can always allow users to buy the "real-money" economy using the ingame currency but require them to have an internet connection. However, if you do allow such a thing then the user can still modify any internal values on their device without you being able to check any of it.

tl;dr Either you trust the user to not hack, or you need to perform online validation of anything relating to real money
> 0 votes

# Answer
What I do is store the data in an obscured and verifiable fashion in memory and on disk, only decoding it when necessary. As mentioned in the comments, this will not prevent alteration, but it will deter it.

For example, an obscured value could be a struct that stores the number twice, once normally and once altered by, for example, XOR-ing it with some key. Then any program trying to alter the value in-memory or on disk would find the first, and modify it. But the next time you try to access the value, some property fetcher would check to see if they match. If they don’t, just forcibly quit the application. That may be sufficient to deter most casual hacking. It would also help if you cryptographically sign your save data and verify that when loading.

However, you also have to worry about users modifying the app code, which would allow them to bypass any check. And if they can see the source decompiled, they can easily determine where your check is and either disable it or figure out how to change the value in the save data on disk. So you would also need to try to obscure your “currency“ class and methods, as well as your loading code so they are harder to find and modify. And if they do manage to modify the game, you can check whether it’s been modified on Android at least by ensuring the signature on the installed package is the one you expect it to be (again, in an obscured way). If not, then you can again force quit, or behave slightly differently so that casual hackers don’t notice anything immediately.

None of these will completely deter someone determined enough, but everything combined together has helped stop many of the problems with games I’ve worked on.
> 3 votes

---
Tags: c#, android, monogame, ios, xamarin
---


# Question
Title: Why is the Tilemap not fitting the screen?
I have a background image which I made it in tiled map editor of width 40tiles and height of 8tiles.When I run the game the tilemap bounces with the player and I can see the black portion of the screen.The game screen width and height is 320 by 256.Here is the problem Play class

# Answer
You'll want to make sure the position of the camera never goes outside the bounds of the map. Find the map's boundaries, then use MathUtils.clamp() on the camera's X and Y positions to ensure this. For example:

```
cam.position.x = MathUtils.clamp(cam.position.x, mapLeftBoundary, mapRightBoundary);
cam.position.y = MathUtils.clamp(cam.position.y, mapBottomBoundary, mapTopBoundary);

```
> 1 votes

# Answer
If you don't want the camera to jump with the player the set the camera Y-position to half the grid height:

```
cam.position.set(player.getPosition().x+40/2 , 8/2,0);
cam.update();

```
> 0 votes

---
Tags: java, libgdx, camera
---


# Question
Title: Error code 1282 when calling glDrawElements
I am trying to render my terrain using an EBO, but the function `glDrawElements` returns an error (`1282`). I tried to find out what is causing the error, but everything seems to be as it should according to my understanding.

In my `ResourceManager` class I load the heightmap and create the EBO and VBO.

```
std::shared_ptr<Terrain> ResourceManager::LoadTerrain(const std::string& filePath)
{
    int nrChannels;
    unsigned int vertexCount;
    int width;
    int length;
    float w = 10.0f, l = 10.0f;
    unsigned char* data = stbi_load(filePath.c_str(),&width, &length,&nrChannels,0);
    std::vector<glm::vec3> vertices(width * length);
    std::vector<unsigned int> triangles;

    if (data == NULL)
    {
        std::cout << "Cannot load the heightmap!" << std::endl;
    }

    for (int z = 0; z < length; z++)
    {
        for (int x = 0; x < width; x++)
        {
            // normalizing the x and z of the vector
            glm::vec3 vertex = glm::vec3(x/(float)width,0,z/(float)length);

            // multiplying by the width and length
            vertex.x *= w;
            vertex.z *= l;
            // shifting the center to be in the center of the object.
            vertex.x -= width/2;
            vertex.z -= length/2;

            vertices[vertexCount] = vertex;

            // unsigned char* pixelOffset = data + (z + this->length * x) * nrChannels;
            // std::cout << "red " << static_cast<unsigned int>(pixelOffset[0]) << std::endl;

            if ((vertexCount+1 % width) != 0 && z+1 < length)
            {
                triangles.push_back(vertexCount);
                triangles.push_back(vertexCount + width);
                triangles.push_back(vertexCount + width + 1);

                triangles.push_back(vertexCount);
                triangles.push_back(vertexCount + width + 1);
                triangles.push_back(vertexCount + 1);
            }
            vertexCount++;
        }
    }
    stbi_image_free(data);

    // OPENGL Part
    GLuint IBO, VBO;
    glGenBuffers(1, &VBO);
    glBindBuffer(GL_ARRAY_BUFFER,VBO);
    glBufferData(GL_ARRAY_BUFFER, sizeof(glm::vec3) * vertices.size(), vertices.data(), GL_STATIC_DRAW);

    glGenBuffers(1, &IBO);
    glBindBuffer(GL_ELEMENT_ARRAY_BUFFER,IBO);
    glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(unsigned int) * triangles.size(), triangles.data(), GL_STATIC_DRAW);

    glEnableVertexAttribArray(0);
    glVertexAttribPointer(0,3,GL_FLOAT,GL_FALSE,12,(void*)0);

    std::shared_ptr<Terrain> terrain = std::make_shared<Terrain>(Terrain(VBO, IBO, triangles.size(), Transform()));
    terrain->transform.SetScale(glm::vec3(1.0f,1.0f,1.0f));
    terrain->transform.SetPosition(glm::vec3(0.0f,0.0f,0.0f));
    for (int i = 0; i < triangles.size(); i++)
    {
        std::cout << triangles[i] << std::endl;
    }
    return terrain;
}

```

The part of the code that generates the error is the following

```
void Terrain::Render()
{
    this->Bind();
    glDrawElements(GL_TRIANGLES,this->indexCount, GL_UNSIGNED_INT, (void*)0);
    std::cout << "after render but before unbind " << glGetError()<< " " << this->indexCount << std::endl;
    this->Unbind();
}

```

`Bind` and `Unbind` are just 2 GL calls.

```
void Terrain::Bind()
{
    glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, this->indexBuffer);
}

void Terrain::Unbind()
{
    glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
}

```

**EDIT :** The code for the rendering is below :

Renderer.cpp

```
void Renderer::Draw(std::unique_ptr<Scene>& scene, std::shared_ptr<Terrain> terrain)
{
    glm::mat4 projection = scene->camera.GetProjectionMatrix();
    glm::mat4 view = scene->camera.GetViewMatrix();
    this->shader.Use();
    this->shader.SetMat4("projection", projection);
    this->shader.SetMat4("view", view);

    this->shader.SetMat4("model", terrain->transform.getWorldMatrix());
    std::cout << glGetError() << std::endl;
    terrain->Render();
    std::cout << glGetError() << "after render" << std::endl;
    for (int i = 0 ; i < scene->gameObjects.size(); i++)
    {
        glm::mat4 model = scene->gameObjects[i]->transform.getWorldMatrix();
        this->shader.SetMat4("model", model);
        scene->gameObjects[i]->Render();
    }
}

```

# Answer
1282 is `GL_INVALID_OPERATION`. This means that the operation you asked OpenGL to perform isn't valid for the set of active state or the given set of parameters to the function. Which, yes, is really broad and unhelpful.

What you can do to diagnose these errors is try to enable the debug output and see if that provides additional information and guidance that leads you to the cause of the error. You can turn on debug output using `glEnable(GL_DEBUG_OUTPUT)` or by creating a debug context.

Then use `glDebugMessageCallback` to hook up a callback that receives the debug output messages, and dump them to a log file or the screen or whatever.
> 3 votes

---
Tags: opengl, rendering, terrain-rendering
---


# Question
Title: Unity C#: Accurate MachineGun Firerate at lower FPS
I have long accepted that my firerate will be more or less irregular and inaccurate. Now that I'm adding sound things are getting really ugly. My methods for getting the firerate are primitive and I need some help in increasing firerate accuracy.

## My Primitive Method #1:

```
float firerate = 0.1f;
float waitfire;

void Update()
{
    waitfire += Time.deltaTime;

    if (waitfire > firerate) //Fires gun everytime timer exceeds firerate
    {
        waitfire = 0;
        Shoot();
    }
}

```

The main issue is that the weapons firerate will be significantly slower than it should. 600 rounds per minute come in as 550, while 1300 rounds per minute come in as 1100. The effect is increased dramatically if frames are reduced, because waitFire will always be higher than firerate, more so if frames are low.

Also when using a Debug.Log() in update for counting frames I get A LOT less frames than in-game. If I'm running 200fps, Unity only does 40-60 passes through update. Is this normal?

The result at ca 35fps: (The weapon was intended to cycle at 600rpm)

https://www.youtube.com/watch?v=I6V5ojTyQVQ

## My primitive Method #2

```
float shootTimeCounter; //Counts time since shooting
float autoShotCounter; //Counts number of shots in automatic fire

float firerate = 0.1f

void Update()
{
    shootTimeCounter += Time.deltaTime;

    if (shootTimeCounter > (autoShotCounter * firerate)
    {
        autoShotCounter ++;
        Shoot();
    }
}

```

Obviously this is not the exact code I am using, I just sketched it in Notepad to properly explain the procedure.

No matter how bad the framerate is, it will shoot 10 shots per second. If frames drop below 10 it will simply fire 2 shots in the same frame. However irregularities are magnified compared to the first method. With Method #2 Time between shots can range between 0.05s and 0.15s. With Method #1 firerate was slower, but at least it stayed above 0.1.

The result also at ca 35fps:

https://www.youtube.com/watch?v=aOapNEaN2I8

## Source Engine

I experimented using fps\_max in Half-Life 2, comparing the firerate when dropping the framerate. I modified the AR2's mag to hold 100 rounds. It cycles 10 rounds per second. This is the duration it took precisely to empty the whole magazine at following frames per second:

```
fps_max 300: 10 seconds
fps_max 10: 10 seconds
fps_max 9: 11.3 seconds
fps_max 8: 12.7

```

There were no irregularities whatsoever in the firerate, only the sound got mangled slightly. So I was sitting there wondering how on earth they managed to pull that off and decided to ask you guys.

# Answer
Your problem occurs because you are resetting the time to 0. Say for example that it should take 30ms forthe next shot to fire and your delta time from the last shot comes out to 32ms, by setting the time back to 0 you are effectively disregarding 2ms of time in the simulation.

Instead you should do waitfire - firerate this way you do not lose the extra milliseconds each time you fire

## Edit: For clarification as to how to handle missing time in the simulation

Once you have this done, you must fire your projectile such that it will simulate the lost time. Say for example your bullet was fired such that waitfire is now at .03 seconds, then this means that the bullet should have been in the simulation for .03 seconds and you therefore need to compensate for that. To do this you simply have to move the bullet forward by however much it should hae in that time step.

If you are scared of missing out on point blank collisions in that time frame then you may also either ray cast the path travelled this way, or add a new collision detection behind the bullet to cover the ground, if this collider gets hit in the first frame then it should have collided, if not then you may safely delete that collider and keep going as if nothing was
> -1 votes

---
Tags: frame-rate, timer, first-person-shooter, shooter, shoot-em-up
---


# Question
Title: Java 2d array to generate grid - java.lang.ArrayIndexOutOfBoundsException: length=4; index=-1
I am creating a Hashi Puzzle game (Islands and Bridges) I am generating a 2d grid with Islands that can be connected using bridges, I am also running a DFS algorithm to check if the map is solvable I am getting this error

> java.lang.ArrayIndexOutOfBoundsException: length=4; index=-1

I am using a 2d array to generate the map,What could cause the error?

Land.java

```
public class Land {

    private int[][] BRIDGES_TO_BUILD;

    private boolean[][] IS_ISLAND;
    private Direction[][] BRIDGES_ALREADY_BUILT;

    public Land(int[][] bridgesToDo){
        BRIDGES_TO_BUILD = copy(bridgesToDo);

        int R = bridgesToDo.length;
        int C = bridgesToDo[0].length;
        BRIDGES_ALREADY_BUILT = new Direction[R][C];
        IS_ISLAND = new boolean[R][C];
        for(int i=0;i<R;i++) {
            for (int j = 0; j < C; j++) {
                BRIDGES_ALREADY_BUILT[i][j] = null;
                IS_ISLAND[i][j] = bridgesToDo[i][j] > 0;
            }
        }
    }

    public Land(Land other){
        BRIDGES_TO_BUILD = copy(other.BRIDGES_TO_BUILD);
        int R = BRIDGES_TO_BUILD.length;
        int C = BRIDGES_TO_BUILD[0].length;
        BRIDGES_ALREADY_BUILT = new Direction[R][C];
        IS_ISLAND = new boolean[R][C];
        for(int i=0;i<R;i++) {
            for (int j = 0; j < C; j++) {
                BRIDGES_ALREADY_BUILT[i][j] = other.BRIDGES_ALREADY_BUILT[i][j];
                IS_ISLAND[i][j] = other.IS_ISLAND[i][j];
            }
        }
    }

    public int[] next(int r, int c, Direction dir){
        int R = BRIDGES_TO_BUILD.length;
        int C = BRIDGES_TO_BUILD[0].length;

        // out of bounds
        if(r < 0 || r >=R || c < 0 || c >= C)
            return null;

        // motion vectors
        int[][] motionVector = {{-1, 0},{0,1},{1,0},{0,-1}};
        int i = Arrays.asList(values()).indexOf(dir);

        // calculate next
        int[] out = new int[]{r + motionVector[i][0], c + motionVector[i][1]};

        r = out[0];
        c = out[1];

        // out of bounds
        if(r < 0 || r >=R || c < 0 || c >= C)
            return null;

        // return
        return out;
    }

    public int[] nextIsland(int r, int c, Direction dir){
        int[] tmp = next(r,c,dir);
        if(tmp == null)
            return null;
        while(!IS_ISLAND[tmp[0]][tmp[1]]){
            tmp = next(tmp[0], tmp[1], dir);
            if(tmp == null)
                return null;
        }
        return tmp;
    }

    public boolean canBuildBridge(int r0, int c0, int r1, int c1){
        if(r0 == r1 && c0 > c1){
            return canBuildBridge(r0, c1, r1, c0);
        }
        if(c0 == c1 && r0 > r1){
            return canBuildBridge(r1, c0, r0, c1);
        }

            if (r0 == r1) {
                int[] tmp = nextIsland(r0, c0, Direction.EAST);
                if (tmp[0] != r1 || tmp[1] != c1)
                    return false;
                if (BRIDGES_TO_BUILD[r0][c0] == 0)
                    return false;
                if (BRIDGES_TO_BUILD[r1][c1] == 0)
                    return false;
                for (int i = c0; i <= c1; i++) {
                    if (IS_ISLAND[r0][i])
                        continue;
                    if (BRIDGES_ALREADY_BUILT[r0][i] == Direction.NORTH)
                        return false;
                }
            }
        if(c0 == c1){
            int[] tmp = nextIsland(r0, c0, Direction.SOUTH);
            if(tmp[0] != r1 || tmp[1] != c1)
                return false;
            if(BRIDGES_TO_BUILD[r0][c0] == 0 || BRIDGES_TO_BUILD[r1][c1] == 0)
                return false;
            for (int i = r0; i <= r1 ; i++) {
                if(IS_ISLAND[i][c0])
                    continue;
                if(BRIDGES_ALREADY_BUILT[i][c0] == EAST) {
                    return false;
                }
            }
        }
        // default
        return true;
    }

    public int[] lowestTodo(){
        int R = BRIDGES_TO_BUILD.length;
        int C = BRIDGES_TO_BUILD[0].length;

        int[] out = {0, 0};
        for (int i=0;i<R;i++) {
            for (int j = 0; j < C; j++) {
                if(BRIDGES_TO_BUILD[i][j] == 0)
                    continue;
                if (BRIDGES_TO_BUILD[out[0]][out[1]] == 0)
                    out = new int[]{i, j};
                if (BRIDGES_TO_BUILD[i][j] < BRIDGES_TO_BUILD[out[0]][out[1]])
                    out = new int[]{i, j};
            }
        }
        if (BRIDGES_TO_BUILD[out[0]][out[1]] == 0) {
                return null;
        }
        return out;
    }

    @TargetApi(Build.VERSION_CODES.GINGERBREAD)
    private int[][] copy(int[][] other){
        int[][] out = new int[other.length][other.length == 0 ? 0 : other[0].length];
        for(int r=0;r<other.length;r++)
            out[r] = Arrays.copyOf(other[r], other[r].length);
        return out;
    }

    public void connect(int r0, int c0, int r1, int c1){
        if(r0 == r1 && c0 > c1){
            connect(r0, c1, r1, c0);
            return;
        }
        if(c0 == c1 && r0 > r1){
            connect(r1, c0, r0, c1);
            return;
        }
        if(!canBuildBridge(r0, c0, r1, c1))
            return;

        BRIDGES_TO_BUILD[r0][c0]--;
        BRIDGES_TO_BUILD[r1][c1]--;

        if(r0 == r1){
            for (int i = c0; i <= c1 ; i++) {
                if(IS_ISLAND[r0][i])
                    continue;
                BRIDGES_ALREADY_BUILT[r0][i] = Direction.EAST;
            }
        }
        if(c0 == c1){
            for (int i = r0; i <= r1 ; i++) {
                if(IS_ISLAND[i][c0])
                    continue;
                BRIDGES_ALREADY_BUILT[i][c0] = Direction.NORTH;
            }
        }
    }
}

```

Search function with Map Generation

```
 public int[][] debug_board_state_easy = new int[4][4];
 void search() {

        Map<Point, List<Direction>> remainingOptions = new HashMap<>();

        Stack<Land> gameTree = new Stack<>();
        gameTree.push(new Land(debug_board_state_easy));

        while (true) {

            Land state = gameTree.peek();
            int[] p = state.lowestTodo();
            if (p == null)
                System.out.println("solution found");

            // move to next game state
            int r = p[0];
            int c = p[1];
            System.out.println("expanding game state for node at (" + r + ", " + c + ")");

            List<Direction> ds;
            if (remainingOptions.containsKey(new Point(r, c)))
                ds = remainingOptions.get(new Point(r, c));
            else {
                ds = new ArrayList<>();
                for (Direction dir : Direction.values()) {
                    int[] tmp = state.nextIsland(r, c, dir);
                    if (tmp == null)
                        continue;
                    if (state.canBuildBridge(r, c, tmp[0], tmp[1]))
                        ds.add(dir);
                }
                remainingOptions.put(new Point(r, c), ds);
            }

            // if the node can no longer be expanded, and backtracking is not possible we quit
            if (ds.isEmpty() && gameTree.isEmpty()) {
                System.out.println("no valid configuration found");
                return;
            }

            // if the node can no longer be expanded, we need to backtrack
            if (ds.isEmpty()) {
                gameTree.pop();
                remainingOptions.remove(new Point(r, c));
                System.out.println("going back to previous decision");
                continue;
            }
            Log.e("gameTree", "WE ARE CRASHING HERE");
            Direction dir = ds.remove(0);
            System.out.println("connecting " + dir.name());
            remainingOptions.put(new Point(r, c), ds);
            Land nextState = new Land(state);
            int[] tmp = state.nextIsland(r, c, dir);
            nextState.connect(r, c, tmp[0], tmp[1]);
            gameTree.push(nextState);
        }
    }

  private void setCurrentState(State new_state) {
    this.current_state = new_state;
  }

  public State getCurrentState() {
    return current_state;
  }
}

    private void InitializeEasy() {
        Random rand = new Random();

        setCurrentState(new State(WIDTH_EASY));
        for (int row = 0; row < debug_board_state_easy.length; row++) {
            for (int column = 0; column < debug_board_state_easy[row].length; column++) {
                debug_board_state_easy[row][column] = Integer.valueOf(rand.nextInt(5));

            }

        }

        for (int row = 0; row < debug_board_state_easy.length; row++) {
            for (int column = 0; column < debug_board_state_easy[row].length; column++) {
                System.out.print(debug_board_state_easy[row][column] + " ");
            }
            System.out.println();

        }
        this.search();
        for (int row = 0; row < WIDTH_EASY; ++row) {
            for (int column = 0; column < WIDTH_EASY; ++column) {

                getCurrentState().board_elements[row][column] = new BoardElement();
                getCurrentState().board_elements[row][column].max_connecting_bridges = Integer.valueOf(debug_board_state_easy[row][column]);
                getCurrentState().board_elements[row][column].row = row;
                getCurrentState().board_elements[row][column].col = column;

                if (getCurrentState().board_elements[row][column].max_connecting_bridges > 0) {
                    getCurrentState().board_elements[row][column].is_island = true;
                }

            }
        }

    }

```

# Answer
> 2 votes
Since the line that throws the exception is

```
int[] out = new int[]{r + motionVector[i][0], c + motionVector[i][1]};

```

we can determine that `motionVector` is the array being indexed (it is the only index operation), and thus it is an array of length 4 that you are attempting to index with the value -1.

The only variable used to index `motionVector` is `i`, so `i` must be -1.

Just above, you have

```
int[][] motionVector = {{-1, 0},{0,1},{1,0},{0,-1}};
int i = Arrays.asList(values()).indexOf(dir);

```

`indexOf` returns -1 if the given object cannot be found in the list, so the root cause here is that you're not able to find `dir` in the list produced by `values()`.

This is likely because `dir` is not one of the four direction values you put into the list, or because the equality operation for `Direction` is wrong or will not compare equal when you expect (note how `indexOf` performs its test).

---
Tags: java, 2d, android, algorithm, grid
---


# Question
Title: How does my program know which variables to link to the shader?
I am using DirectX and C++. I never understood how my VertexDeclaration knew what variables were the UV map and which were linked to the position. I have in my shader Position : POSITION and Texture : TEXCOORD1

In my variables for vertex format I have int X, Y, Z, U, V.

In my declaration I have

```
    D3DVERTEXELEMENT9 Decl[] =
    {
        {
            0,
            0,
            D3DDECLTYPE_FLOAT3,
            D3DDECLMETHOD_DEFAULT,
            D3DDECLUSAGE_POSITION,
            0
        },
        {
            0,
            0,
            D3DDECLTYPE_FLOAT2,
            D3DDECLMETHOD_DEFAULT,
            D3DDECLUSAGE_TEXCOORD,
            0
        },
      D3DDECL_END()
   };

```

My FVF is D3DFVF\_XYZ | D3DFVF\_TEX1

How does it know to link X, Y, Z with position? and U, V with the first texcoord? What would the variables for the second texcoord be? Is there some pattern?

# Answer
> 2 votes
FVF flags are mapped 1:1 to interleaved elements of the vertices in your stream source. The order is a bit undocumented and seems to be assumed to be the same order as the FVF flags are defined in the headers.

They're tightly packed with alignment constraints, and as such, if you have (D3DFVF\_XYZ | D3DFVF\_TEX1), for each vertex, it expects three position floats, followed by two (by default) texture coordinate floats.

It expects attributes to be tightly packed, with some additional restrictions on which elements may appear on some shader models (if you're

There's no "linking of variables" to be made, it just expects things at offsets computable from the FVF flag set.

For a tabular mapping of individual FVF flags to elements, see this MSDN page.

For texture coordinate sets, the FVF\_TEXn flag indicates the number of texture coordinate sets you provide. If you want 2 sets of texture coordinates, you use FVF\_TEX2 only, and at the texture coordinate part of your vertex struct, you have two texture coordinate set worth of values.

That is, the following FVF part indicates that you have two texture coordinate parts

* the first (#0) with 3 elements (S,T,P),
* the second (#1) with two (S,T):

D3DFVF\_TEX2 | D3DFVF\_TEXCOORDSIZE3(0) | D3DFVF\_TEXCOORDSIZE2(1)

mapping to a struct that has (S0,T0,P0,S1,T1) at the end.

I echo the sentiment of the other answers, however. Avoid FVFs if you target D3D9, there's no reason to have them outside of legacy code.

# Answer
> 1 votes
You shouldn't mix vertex declarations with FVF codes - it's a case of use either but not both. Vertex declarations are highly recommended for the additional flexibility they offer.

For a declaration it matches the HLSL semantic with the Usage and UsageIndex members of your D3DVERTEXELEMENT9 declaration. So for a semantic of TEXCOORD0 we're looking for a D3DDECLUSAGE\_TEXCOORD at UsageIndex 0.

When matching these to your vertex struct the Stream and Offset members of D3DVERTEXELEMENT9 are used.

**Update**

More info is needed, so here we go.

Let's say that we have a struct declared like so:

```
struct myVertex
{
    float position[3];
    float texcoord[2];
};

```

In order to map this to a vertex declaration, you use an array of 2 D3DVERTEXELEMENT9 when creating the declaration. The first one looks like this:

```
{0, 0, D3DDECLTYPE_FLOAT3, D3DDECLMETHOD_DEFAULT, D3DDECLUSAGE_POSITION, 0}

```

Stream 0 we'll ignore for now.

Offset 0 means that position starts 0 bytes from the beginning of the vertex data. That's right at the start of "float position\[3\]" in your struct.

We'll also ignore D3DDECLTYPE\_FLOAT3 (that's just telling D3D that it's 3 floats) and D3DDECLMETHOD\_DEFAULT.

D3DDECLUSAGE\_POSITION means that it maps to the "POSITION" semantic in your HLSL, and the final 0 means that it maps specifically to "POSITION0".

On to the second one (texcoords) and here it is:

```
{0, 12, D3DDECLTYPE_FLOAT2, D3DDECLMETHOD_DEFAULT, D3DDECLUSAGE_TEXCOORD, 0}

```

Again we've got Stream 0 and we'll ignore it for now.

Offset 12 - this is where it tells D3D which struct members to use for texcoords. This is now 12 bytes from the beginning of the vertex data, and - looking back at our struct definition - we see that the first member is "float position\[3\]". Assuming that a float is 4 bytes (it always will be on Windows), 3 floats is 12 bytes, so also assuming that the struct is tightly packed, we then know that texcoords begin at the 12th byte of the vertex data, which is "float texcoord\[2\]".

Again, D3DDECLTYPE\_FLOAT2 just says that this is two floats, and we'll ignore D3DDECLMETHOD\_DEFAULT.

D3DDECLUSAGE\_TEXCOORD is here and it has UsageIndex 0 so that maps to the "TEXCOORD0" HLSL semantic (if UsageIndex was 1 it would be "TEXCOORD1").

For FVF codes D3D does it's own work behind the scenes in a similar manner, but you shouldn't be using FVF codes at all.

# Answer
> 0 votes
How does it know `x,y,z` are position and `u,v` texture coords? It doesn't. You are the one saying so. And you do that (incorrectly in the example you provided) through the `Offset` member of the `D3DVERTEXELEMENT9` struct. That is the offset in bytes from the start of the struct until the first variable that represents something.

Read Maximus Minimus answer. He explains it perfectly. But just to be clear, supposing your struct is something like

```
struct Vertex
{
    float x; // offset 0 - start of position coords
    float y; // offset 4
    float z; // offset 8
    float u; // offset 12 - start of texture coords
    float v; // offset 16
};

```

So, as long as your struct was created in a sane way, and the variables are declared sequentially, all you have to do is to inform the correct offset. I strongly recommend you to read Maximus Minimus answer again (and accept it)

---
Tags: c++, directx
---


# Question
Title: Getting an object to move in another objects direction
I have a player and an enemy, both have x and y values, and I want to move the enemy to the player and have them 'touch' over time in a speed that I can determine, I tried calculating the angle between the enemy, the player, and the 0, 0 point on the canvas using trigonometry but it just doesn't work right, most the times the angle is Not A Number(NaN) or goes in a direction different that the player. \*The code is not in the same file, I copy pasted the relevant parts of the code and pasted them together. Here is my code, any help would be greatly appreciated:

```
// Creating a visual triangle and storing the length of it's vertices distance(size)
    line(enemy.x, enemy.y, 0, 0);
    lineOne = dist(enemy.x, enemy.y, 0, 0);
    line(player.x, player.y, 0, 0);
    lineTwo = dist(player.x, player.y, 0, 0);
    line(player.x, player.y, enemy.x, enemy.y);
    lineThree = dist(player.x, player.y, enemy.x, enemy.y);
// Calculating the angle itself using the cosine rule
angle = acos((lineThree * lineThree + lineOne * lineOne - lineTwo * lineTwo) / (2 * lineThree * lineTwo));

//Function to move  the enemy(based on a suggestion made in this website)
this.move = function()
    {
        if(angle != NaN && angle >= 0)
        {
            this.x -= 2 * cos(angle) + sin(angle) * 2;
            this.y += 2 * sin(angle) + cos(angle) * 2;
        }
    }

```

The if statement that checks if the angle is not a NaN value is required because it happens a lot for some reason, it also checks if it is bigger or equal to zero, because if it isn't the enemy just doesn't show at all.

Thank you for your time!

# Answer
You're overcomplicating it. Let's say the object you want to move is at `(x1; y1)` and the player is at `(x2; y2)`

The vector pointing from the object to the player is `d = (x2 - x1; y2 - y1)` you can normalize this by dividing by it's own length: `normalized = d / |d|`. And then just multiply it with a speed value and add it to the object's position.

Even if you wanted to calcilate the angle (which you don't need in this case) you could just get the distances of the player and the object on the x and y axis and use atan2 to find the angle: `angle = atan2(y2 - y1, x2 - x1)`

Also, converting an angle to a vector is a lot easier too, the vector pointing in that direction would simply be `(cos(angle); sin(angle))`
> 2 votes

---
Tags: javascript, algorithm, trigonometry
---


title: How to detect speed on collision

text:
# Question
Title: How to detect speed on collision
The problem with OnCollisionEnter2d is that it only gets called when there is a collision but what I wanted is to get the current speed of object at the moment of impact until the object stops moving. So that I if the object stops moving after impact I will call another function.

```
void OnCollisionEnter2d(Collision2D collision){
   Debug.Log(speed); //problem this will only give the speed at the moment of impact
   if(speed <= 0){
     blah blah
   }
}

```

I also tried putting speed variable on the Update()

```
void Update(){
     var currentVelocity = player_rb.velocity;
     speed = currentVelocity.magnitude;
}

```

# Answer
You could use a Coroutine

```
void OnCollisionEnter2d(Collision2D collision){
   StartCoroutine(DoSomethingWhenStopped());
}

IEnumerator DoSomethingWhenStopped(){
    yield return new WaitUntil(() => player_rb.velocity.magnitude <= 0.01);
    DoSomething();
}

```

https://docs.unity3d.com/ScriptReference/WaitUntil.html
> 1 votes

---
Tags: unity
---


title: Event queue: tell or ask?

text:
# Question
Title: Event queue: tell or ask?
I'm working my way through a lot of game development resources, coming from a completely different field of software development, I'm interested in learning what patterns are frequently used in game development, and which aren't.

During my research, I wanted to know if/how event queues are handled in games, and came across Game Programming Patterns' post about Event Queues. (as an aside, what an awesome resource that book is!)

In it, Bob Nystrom gives an example of a "play audio" queue, where one part of the system can produce/enqueue the playing of an audio fragment, and the audio handler/consumer can act on that request whenever it can.

I like this pattern a lot, but the end-result still feels like it results in domains being crossed, because the sender (in this example the part of the system that deals with a unit dying) has to *ask* the audio system to play the "deathSoundID" sound using `playSound(deathSoundID)` (which, in this case, then enqueues that request for the audio engine to pick up as soon as it can).

What I expected to be proposed is that the sender in this case *tells* the audio engine that an event occurred (by having the audio engine listen for events from this specific game system), at which point the audio engine can then determine if/how it wants to act on that specific event.

Now, admittedly, there's still crossing of domains here, as in my example, the audio engine now has to have some kind of (huge) case statement that couples any game event to an audio-related action, but you no longer have to litter unrelated functions with calls to `playSound`, and it also forces you to be a good citizen, and allow other systems to act on whatever action you just took, be it the audio engine in this case, or the "gamepad rumbler" engine that wants to rumble your gamepad because you've just slain a large enemy.

Another downside to this is that you need many more queues for all your systems (if you want to avoid some kind of global event queue, which I think you should), which might not be practical/performant enough to do, so perhaps that's the reason why it wasn't chosen here.

Either way, as a newcomer to game development, I'm interested to hear why one would be preferable over the other, and in what situations that would be the case.

# Answer
Telling the audio system that an event occurred (versus *demanding* that the audio system play this sound right now) is generally preferable because it lets the audio system make the final determination about whether or not/how to play the sound. Whether that looks like "posting a request" or "posting an event" is largely a semantic issue. The important part, as you note, is that the audio system gets to decide the specifics.

Audio engineers typically have limitations to work with that are both technical and physical. Technically, the engine may only support playing *N* sounds simultaneously, and physically a player may only want to hear *M* sounds at the same time (otherwise it sounds like noise). Similar restrictions exist for background music tracks.

Gameplay code that triggers a character death probably isn't aware of what else is going on in the world, audio-wise, and so by telling the audio system "a death sound should play," the audio system can look up the priority assigned to death sounds and decide if that sound gets to override any other sounds currently playing, or if it needs to reduce the volume on the background music track, or if it needs to mix that sound in with some other enqueued sounds to reduce the total number of audio buffers being streamed to fit some technical constraint.

All of those priorities and mixes and overrides are usually defined in data controlled by the audio engineers who oversee that domain; it's better to have that data (and it is data, in a production-scale system, not "one big case statement," although the concept is basically the same) localized in one spot *there*, for them (via tools like Wwise) than to scatter it around a bunch of areas in the gameplay code.

For similar reasons, game code will often want to say "play *a* death sound" rather than "play `screaming_burning_on_fire_omg.wav` because it will let audio engineers control sound variations, randomness, pitch shifting based on other audio events and queues, from within their data rather than having to poke around in a bunch of different areas in code or data.

For games with smaller, perhaps one-person teams, this kind of organization is maybe less useful. But for any larger-scale project where there is a dedicated team working on the audio, that team will likely prefer the approach where they get to actually make the decisions about how the audio works.
> 4 votes

# Answer
There's a lot to balance in practical game development.

## Generic event system vs domain-specific:

One doesn't preclude the other.

You can use a generic queue system:

```
audioQueue.SendEvent("PlaySound", deathSoundID);

```

And wrap it in a convenient function:

```
void playSound(ID_TYPE soundID) {
    audioQueue.SendEvent("PlaySound", soundID);
}

//...

playSound(deathSoundID);

```

By wrapping a generic message system into domain-specific API calls we get the advantage of a tested and debugged generic message system while keeping the code very **readable at-a-glance** and easily refactor-able.

## Decision making

It can be up to the sender, the receiver, or both. We can even add a 3rd layer in between the two ends to add for example a context-aware filter.

eg: Turn playSound() from global function to a local member function of actor object that can make more decisions, and then call the global playSound() function.

The receiver (audio system) can decide to ignore the message or alter its interpretation.

The message parameter `soundID` can be either a specific sound or a class of sound, it's really up to the receiver.

The message can be an order to play a sound or a request to play a sound, again it's up to the receiver.

## Redirection

Nothing prevents the audio system from sending rumble commands as part of the sound effect processing.

In fact, the rumble motor is just a very low-frequency sound generator and some advanced haptic-feedback use low-frequency weighted solenoids (essentially a "speaker" without a diaphragm).

So we're not even breaking out the audio concept nor functionality.

If you feel things would be more manageable with one more abstraction you can create an "effect" system that then sends events to other sub-systems.

But too many abstraction layers can make it very difficult to know what's happening and why.

## Domain-Crossing

"Perfect is the enemy of good."

You'll always have domain-crossing: Things have to talk to one another.

The best practice is to keep it to a minimum, not to eliminate it completely which is not possible.

## Separation of Concerns

The important part here is to keep game-specific logic out of the lower generic/reusable engine code.

You can add callback-functions and/or data-driven masks, remapping tables, and settings if game-specific context-sensitive decisions/tweaks are needed so the engine-level code remains game-agnostic.

ie: If one level needs a particular sound remapped, a remapping table feature can be added to the audio engine. The audio engine doesn't "know" it's on the "Fire Level" it just knows it has to remap the sound. It's up to something inside that level on the game-side to enable/disable the remapping.
> 2 votes

---
Tags: architecture, performance, design-patterns, events, messaging
---


# Question
Title: How to implement level-player collisions resolution?
I want to create simple collision response system (physical simulation is not required now). It is needed just that player can't go through walls.

I consider some variants: \- Just create a set of primitive colliders (like AABB, OBB, Spheres) and check collisions in every frame (this approach is impemented now) \- Create a BVH for the big level mesh and check collisions with small set of triangles. \- Combine these two approaches and use BVH for determine which colliders I need to check.

But, probably, these variants are wrong. What algorithms and appoaches would you advice for this purpose?

# Answer
In my experience, collisions that involve concave meshes sooner or later gets you in a mess.

If I were you, I would keep your current approach of tests that involve convex shapes: there is no ambiguity about inside/outside, and no nasty stuff like self intersecting meshes.

Just make it so that everything in your world has two representations: a visual model that can be as fancy, and as concave as you like.

The other representation for collisions, which is purely a collection of convex shapes, and only roughly follows the object's shape.

As an example: the visual model of an exquisite Edwardian table could be 4000 triangles. But it's physics shape is just 5 boxes.

The worst thing you could do is collide an arbitrary mesh against another arbitrary mesh. It's wasteful, and leads to horrible collision responses.

One more note: Convex dynamic objects against a static concave terrain mesh is often acceptable though. But if your terrain is a bunch of rooms that can adequately be described with boxes, I wouldn't even do that.
> 2 votes

---
Tags: collision-detection, physics, mathematics, geometry
---


title: How ID's work in FPS games

text:
# Question
Title: How ID's work in FPS games
I am wondering how games generate IDs/GUIDs for their entities (along these lines), and which entities specifically get them. To narrow the scope of the question down, I am just focusing on FPS games such as Halo. This was an earlier question that helps explain how state is synced across clients in an FPS:

The state that is synced when a window is broken in a FPS game

The goal with that question was to learn what kinds of data is sent around to sync clients. The piece that is still missing for me is what entities in the game actually get an ID of some sort (either a GUID, or a scoped ID such as some incremented integer or something).

Some of the game "entities" I am considering are:

* Particles of light, individual pixels, physical forces, etc. (the lowest level vectors/points for calculating light or physics stuff).
* Topology (mountains, roads, etc.).
* Landscape features (grass, bushes, trees, rocks, water, rain drops, etc.).
* City features (cars, signs, buildings, windows, shards of glass from a broken window, etc.).
* Tools / items (weapons, potions, etc.).
* Other players.

It seems that some of these "entities" you can interact with (e.g. destroying a car in GTA, or the other players in the game), some you can *to some degree* (i.e. bushes might sway when you walk by, but you can't shoot them for example), and some you cannot (like the sun in a skybox).

I am thinking in terms of state syncing, it seems like there must be IDs somewhere in the picture so you can map a game entity from computer A to the same game entity in computer B. Even without syncing, it seems like you might want some sort of IDs on objects to allow for easier handling of events and tracking objects. But at the same time I don't really see "IDs" in simple "game engines" like these JavaScript game engines, so that is why I'm asking the question.

The question is, for large games like Halo, what the entities are that have IDs (or some of the main ones), and if the IDs are GUIDs (or generally what kind of ID they are: incremented integers, random numbers, UUIDs, etc.).

Like I'm wondering, maybe *bushes* have IDs. Maybe the individual leaves on the bushes have IDs. Maybe every single triangle in the graphics has an ID. That's what I'm wondering. Maybe the shards of glass have IDs because you can pick them up. Maybe only the players have IDs for some reason. Etc.

I am interested because (a) it seems like IDs are necessary in different ways (for state syncing, for tracking player behavior with different entity types to improve the game experience, etc.), and (b) there is a lot of variation in performance when it comes to using IDs. For example, I just tried generating 1 million particles like this and got these results:

1. `crypto.getRandomValues`: 5.7 seconds to generate 1 million IDs.
2. `Math.random()`: 18ms to generate 1 million IDs.
3. `i++`: 5ms to generate 1 million IDs.

In addition, there is the space constraint, so by using `i++` you can use fewer bits for the ID until it gets very large, but they don't work as GUIDs so you need to do extra work to create ID "scopes" or things like that. Anyways, I would like to figure out how to deal with IDs in games, and looking to FPS as an example to demonstrate where the IDs might be used. Any help would be appreciated. Thank you.

If it is a complicated topic (I'm not sure), then just knowing roughly an outline of how it is typically done, or even a place to look for more information, would be helpful. Also, just saw how Unity is a good example of a Component/Entity system, so maybe instead of FPS a better example is how generic game engines do it. Either way, whatever helps explain how it works.

# Answer
Generally entity IDs are simply generated by incrementing an integer starting at some base value (0, or 1 if you want 0 to mean "no entity"). In other words, your `++i` approach. Some games may "bucket" the integer space by type, for example by saying that "characters will use IDs 100 to 999, bullets will use IDs 1000 though 1999" and so on. This kind of grouping may or may not be necessary, it all depends on how the game works.

This approach is fast and easy, fits well with the typical desire to store objects in big, contiguous arrays indexed by ID, and is deterministic as long as the call order is also deterministic.

When you need actual, full-on GUIDs, version 4 GUIDs are generally used are produced by appropriate standard or third-party APIs (such as C#'s `Guid.NewGuid()` function). You may want these if you need to generate IDs that are keys in a database, or unique across gameplay sessions, et cetera.

Random generation of integer IDs is rarely useful, and often very problematic.

---

As for what *gets* an ID? That depends on the game. An ID is really only needed if the object will need to be referred to on its own, independently of any kind of parent/child hierarchy or whatever. Something like leaves on a bush will probably not be separate entities with their own ID -- they probably won't exist as anything but random vertices on a bush static mesh that has an entity ID. But maybe in a game where splitting individual leaves off a bush is a critical aspect of gameplay, they'll get IDs and be first-class entities.

It really depends on the needs of the game.
> 1 votes

# Answer
GUIDs and IDs (using integer iterators) have the same purpose, but are generated differently. GUIDs, consisting generally of alphanumeric characters, might present collisions on the same client (not good!). While GUIDs might present collisions on the same client, they usually prevent collisions on different clients:

* Client A generate a random GUID using multiple paramenters such as time, some info from hardware, the time the game was open, etc.
* Client B generate a random GUID using the same parameters, but since they (probably) have a different hardware, and didn't open the game at exactly same time, they will have a different GUID!

IDs from integer iterators are much more safe in the case of preventing collisions in the same client, since a collision will only happen during integer overflow (the integer reached the maximum value, and will start from 0 again).

On the other hand, IDs from integer iterators need to be sanitized in multiplayer cases, otherwise the clients will have IDs that collide since both are starting from 0. Solutions for this:

* Only one client will generate IDs, and will send a new ID when other client asks.
* Each client use their own ID iterator, but they use another information to avoid the collisions. This information could be the IP address from the other client.

> Particles of light, individual pixels, physical forces, etc. (the lowest level vectors/points for calculating light or physics stuff).

There's (almost) no reason to sync visual effects between two clients.

> Topology (mountains, roads, etc.). Landscape features (grass, bushes, trees, rocks, water, rain drops, etc.). City features (cars, signs, buildings, windows, shards of glass from a broken window, etc.).

Maps, in general, are not synchronized, unless they are destructible. If the maps are pre-made, and exists in both clients, one client just send to the name of the map they are going to play. If the map is procedurally generated, then it's sent at the beginning of the round.

If some parts of the map are destructible, then you will need an ID for them, to inform the other client which part was destroyed and that should be synchronized. If in client A, a wall of ID 3 was destroyed and generated 10 pieces of rock flying around (with their own ID) and a smoke effect, a message will be sent to client B informing that wall of ID 10 was destroyed, and to generate the 10 pieces of rock with those IDs sent. There will be no message informing to create a smoke effect, because they are not gameplay-critical, the smoke, without ID and synchronization, will be created in client B when the wall is destroyed. The rocks flying around are objects that can be interacted with: if the player is hit by a rock, the player loses HP, or the player could pick a rock to throw in another player, for example. Therefore, the rocks have IDs and are synchronized, because they are gameplay-critical objects.

> Tools / items (weapons, potions, etc.).

Most of the time, these objects have their own ID, and are synchronized between clients.

> Other players.

Definitely have IDs.

In other words, entities that are both "interactible" and have gameplay importance, should have an ID.

> In addition, there is the space constraint, so by using i++ you can use fewer bits for the ID until it gets very large, but they don't work as GUIDs so you need to do extra work to create ID "scopes" or things like that. Anyways, I would like to figure out how to deal with IDs in games, and looking to FPS as an example to demonstrate where the IDs might be used. Any help would be appreciated. Thank you.

If you are using a 64-bits unsigned integer, the maximum value you can have is `18.446.744.073.709.551.615`. If you create 1000 objects per frame, and each second has 60 frames, it will take 3.0744573456×10¹⁴ years to reach the maximum number of IDs. In most cases, it's a number to big that you could use the same iterator for every object, no matter the type, in the world.
> 0 votes

---
Tags: networking, multiplayer, entity-system, game-state
---