title: Find possible paths in a grid

text:
# Question
Title: Find possible paths in a grid
I want to make a simple maze with colour-coded cells:

* white denotes a blank space,
* black denotes a wall,
* green denotes source and
* red denotes destination.

So, my idea was to write an array of integers and replace each integer with its corresponding colour. Example:

```
var maze = [[2, 0, 0], [1, 1, 1], [1, 1, 3]]

```

0, 1, 2, 3 corresponds to wall, space, source, destination respectively

To achieve this, I think I could find all paths in the maze then choose one to make it the solution, and alter a value in each of the remaining paths to make them invalid, only if that value is not included the solution.

I decided to generate each maze with specified width and height, then choose both the source and the destination cells, and finally randomly assign each cell to be either a space or a wall.

The challenging part was to check if any paths exist in the maze, and to return them. If there are no solutions, generate another maze. However, I don't know how to do this yet.

I searched and I found solutions to this problems using breadth first search algorithm, but I don't know how successfully I can return all possible paths.

Simple paths' output for the above maze would be something like this:

```
[Vector2(0, 0), Vector2(1, 0), Vector2(1, 1), Vector2(1, 2), Vector2(2, 2)]
[Vector2(0, 0), Vector2(1, 0), Vector2(1, 1), Vector2(2, 1), Vector2(2, 2)]
[Vector2(0, 0), Vector2(1, 0), Vector2(2, 0), Vector2(2, 1), Vector2(2, 2)]
[Vector2(0, 0), Vector2(1, 0), Vector2(2, 0), Vector2(2, 1), Vector2(1, 1), Vector2(1, 2), Vector2(2, 2)]

```

What I have done so far:

```
func getNeighbors(cell, maze):
    for i in range(maze.size()):
        for j in range(maze[i].size()):
            if maze[cell.x][cell.y] == wall:
                return
            # add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
    return neighbors

func bfs():
    var queue = []
    var source = Vector2(0, 0)
    var destination = Vector2(2, 2)
    queue.append(source)
    while queue.size() > 0:
        var current = queue.pop_back()
        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            queue.append(n)

```

I didn't understand the "visited cells" part of the algorithm. Also, I don't know how to save each path in an array of `possible_paths`.

# Answer
I'm writing this answer with the intent to help you learn.

Yet, I should say DMGregory is correct. Pick an algorithm based on what you want for your game. And might get rid of the invalidation process entirely too.

---

## On your solution

In the spirit of teaching and learning, I'll look at your implementation. *I'll also point out that Godot can has an A\* solution built-in. I'll get to that.*

---

**Getting the Neighbors**

As you have correctly identified, you need to be able to query which are the valid neighbors for a cell.

But this is not right:

```
func getNeighbors(cell, maze):
    for i in range(maze.size()):
        for j in range(maze[i].size()):
            if maze[cell.x][cell.y] == wall:
                return
            # add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
    return neighbors

```

Here you are adding to - presumably - a field `neighbors`, which you also return. So the field `neighbors` would have all the elements added across all the calls to `getNeighbors`, including duplicates. And, remember, we only want the neighbors of the specific cell.

So, first of all, make `neighbors` local (I have also added types to the signature):

```
func getNeighbors(cell:Vector2, maze:Array) -> Array:
    var neighbors := []
    for i in range(maze.size()):
        for j in range(maze[i].size()):
            if maze[cell.x][cell.y] == wall:
                return
            # add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
    return neighbors

```

Second, you don't need to iterate over the whole maze to find the neighbors. You only need to check adjacent cells (to which the comment you have alludes to). So do that:

```
func getNeighbors(cell:Vector2, maze:Array) -> Array:
    var neighbors := []
    for i in [cell.x - 1, cell.x, cell.x + 1]:
        for j in [cell.y - 1, cell.y, cell.y + 1]:
            if maze[i][j] == wall:
                return
            # add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
    return neighbors

```

Wait a minute. Something tells me your maze is rows not columns. Look you have it defined like this:

```
var maze = [[2, 0, 0], [1, 1, 1], [1, 1, 3]]

```

Rearrange and it is like this:

```
var maze = [
    [2, 0, 0],
    [1, 1, 1],
    [1, 1, 3]
]

```

So the outer array is the vertical, and the inner is the horizontal. Thus, it is like this:

```
func getNeighbors(cell:Vector2, maze:Array) -> Array:
    var neighbors := []
    for i in [cell.x - 1, cell.x, cell.x + 1]:
        for j in [cell.y - 1, cell.y, cell.y + 1]:
            if maze[j][i] == wall:
                return
            # add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
    return neighbors

```

Better yet:

```
func getNeighbors(cell:Vector2, maze:Array) -> Array:
    var neighbors := []
    for j in [cell.y - 1, cell.y, cell.y + 1]:
        for i in [cell.x - 1, cell.x, cell.x + 1]:
            if maze[j][i] == wall:
                return
            # add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
    return neighbors

```

Ah, skip the cell itself:

```
func getNeighbors(cell:Vector2, maze:Array) -> Array:
    var neighbors := []
    for j in [cell.y - 1, cell.y, cell.y + 1]:
        for i in [cell.x - 1, cell.x, cell.x + 1]:
            if i == cell.x and j == cell.y:
                continue

            if maze[j][i] == wall:
                return
            # add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
    return neighbors

```

Skip walls. Don't exit on walls:

```
func getNeighbors(cell:Vector2, maze:Array) -> Array:
    var neighbors := []
    for j in [cell.y - 1, cell.y, cell.y + 1]:
        for i in [cell.x - 1, cell.x, cell.x + 1]:
            if i == cell.x and j == cell.y:
                continue

            if maze[j][i] == wall:
                continue

            # add neighbors (x+1, y) (x-1, y) (x, y-1), (x, y+1) if they are within range of width and height
    return neighbors

```

And, yes, add to the neighbors:

```
func getNeighbors(cell:Vector2, maze:Array) -> Array:
    var neighbors := []
    for j in [cell.y - 1, cell.y, cell.y + 1]:
        for i in [cell.x - 1, cell.x, cell.x + 1]:
            if i == cell.x and j == cell.y:
                continue

            if maze[j][i] == wall:
                continue

            neighbors.append(Vector2(i, j))

    return neighbors

```

---

**Interlude: Dictionary**

Let me introduce you to `Dictionary`.

You can declare a `Dictionary` like this:

```
var dict := {}

```

Or like this:

```
var dict := Dictionary.new()

```

You can set (adds if the element is not there) elements like this:

```
dict[key] = value

```

And you can get elements like this:

```
value = dict[key]

```

Crucially, the dictionary won't store two elements on the same key. There will not be duplicated keys. If I do this:

```
dict[key] = value
dict[key] = another_value

```

The second replaces the first one.

You might want to check if the element is there (since getting a elements that isn't there is an error):

```
if dict.has(key):
    value = dict[key]

```

Or you can use `get` which lets you define a fallback which is returned if the element isn't there:

```
value = dict.get(key, fallback)

```

Oh, and you remove from the dictionary like this:

```
dict.erase(key)

```

---

Therefore, we add whatever (e.g. `null` or `true`) we can use the keys as a set. Thus, this is a set:

```
var set := {}

```

You add an element to the set like this:

```
set[value] = true

```

Note that the set cannot have a value twice.

You remove an element from the set like this:

```
set.erase(value)

```

And you check if the set has a value like this:

```
set.has(value)

```

This is faster than adding the elements to an `Array` and then checking if the `Array` has the elements (with `has`) because looking in the array requires Godot to iterate over it, but for the set... I mean `Dictionary` Godot creates an index for quick lookup.

---

**Breadth-first search**

Ok, let us look to your code:

```
func bfs():
    var queue = []
    var source = Vector2(0, 0)
    var destination = Vector2(2, 2)
    queue.append(source)
    while queue.size() > 0:
        var current = queue.pop_back()
        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            queue.append(n)

```

Hmm… You are hard-coding source and destination. Why do you have them in the maze then? Those are two sources of truth. That is not good, because it means that you need to update in two different places if it changes (and if you forget, or you do it wrong, you got a bug).

I'll promote them to parameters. The method call this can pass them. In fact the method that calls this can both pass them and also write them to the maze.

```
func bfs(source:Vector2, destination:Vector2):
    var queue = []
    queue.append(source)
    while queue.size() > 0:
        var current = queue.pop_back()
        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            queue.append(n)

```

In fact, traditionally the graph maze is a parameter too. You made it a parameter in the prior method, so why not here too?

```
func bfs(maze:Array, source:Vector2, destination:Vector2):
    var queue = []
    queue.append(source)
    while queue.size() > 0:
        var current = queue.pop_back()
        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            queue.append(n)

```

On your main issue: visited cells. You need to know which cells you have explored already. How to do that? The simplest solution is to add them to an `Array`… But we will use a set, I mean a `Dictionary`.

```
func bfs(maze:Array, source:Vector2, destination:Vector2):
    var queue := []
    var visited_cells := {}
    queue.append(source)
    while queue.size() > 0:
        var current = queue.pop_back()
        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            queue.append(n)

```

And the `source` should be marked visited right away:

```
func bfs(maze:Array, source:Vector2, destination:Vector2):
    var queue := []
    var visited_cells := {}
    visited_cells[source] = true
    queue.append(source)
    while queue.size() > 0:
        var current = queue.pop_back()
        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            queue.append(n)

```

And yes, you add the source to the queue. I'll leave it as you have it, but know you could have done `var queue := [source]`.

We iterate until the queue is empty. Again, I'll leave it as you have it, but know there is an `empty` method you can use.

And you dequeue… `pop_back` removes and returns the last element. And `append` adds at the end. Thus, the combination of `pop_back` and `append` means you are using your `Array` as a stack not as a queue.

There are two built-in ways to use an `Array` as a queue:

* With `pop_back` and `push_front`.
* With `pop_front` and `push_back` (`append`).

*We could take our time and implement something else (pre-allocate and use indexing), but let's do with what is available already since it is less error prone (look into it if you want).*

Operations on the back of the `Array` are faster. Although we will do both operations equally as much (we will remove everything we add), I'll add at the back since it is in the inner loop (I expect elements to be added in quick succession, at least at the start). Thus:

```
func bfs(maze:Array, source:Vector2, destination:Vector2):
    var queue := []
    var visited_cells := {}
    visited_cells[source] = true
    queue.append(source)
    while queue.size() > 0:
        var current:Vector2 = queue.pop_front()
        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            queue.append(n)

```

Next we check if it is the goal. If it is, we return the path… Wait, we also need to declare the path we are going to return! That is an issue, because we will actually be building multiple paths. Well, we can use a `Dictionary` for this… But for the moment I'll return an empty path.

```
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
    var paths := {}
    var queue := []
    var visited_cells := {}
    visited_cells[source] = true
    queue.append(source)
    while queue.size() > 0:
        var current:Vector2 = queue.pop_front()
        if current == destination:
            return [] # TODO

        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            queue.append(n)

    return [] # TODO

```

Yes, we iterate over the neighbors. And we skip the ones that we visited:

```
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
    var paths := {}
    var queue := []
    var visited_cells := {}
    visited_cells[source] = true
    queue.append(source)
    while queue.size() > 0:
        var current:Vector2 = queue.pop_front()
        if current == destination:
            return [] # TODO

        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            if visited_cells.has(n):
                continue

            queue.append(n)

    return [] # TODO

```

Now we mark the cell as visited:

```
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
    var paths := {}
    var queue := []
    var visited_cells := {}
    visited_cells[source] = true
    queue.append(source)
    while queue.size() > 0:
        var current:Vector2 = queue.pop_front()
        if current == destination:
            return [] # TODO

        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            if visited_cells.has(n):
                continue

            visited_cells[n] = true
            queue.append(n)

    return [] # TODO

```

We make the… *current the parent of the neighbor* … What we are doing is the path up to the neighbor. That is, we need to say that to get to the neighbor, we first need to get to the current cell.

And I said we will use a `Dictionary` for the paths. The plan is to use the cells as keys, and store the paths as values. So, first of all, the path to get to the source, is just the source:

```
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
    var paths := {}
    var queue := []
    var visited_cells := {}
    visited_cells[source] = true
    queue.append(source)
    paths[source] = [source]
    while queue.size() > 0:
        var current:Vector2 = queue.pop_front()
        if current == destination:
            return [] # TODO

        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            if visited_cells.has(n):
                continue

            visited_cells[n] = true
            queue.append(n)

    return [] # TODO

```

Let me re-arrange that:

```
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
    var queue := []
    queue.append(source)

    var visited_cells := {}
    visited_cells[source] = true

    var paths := {}
    paths[source] = [source]

    while queue.size() > 0:
        var current:Vector2 = queue.pop_front()
        if current == destination:
            return [] # TODO

        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            if visited_cells.has(n):
                continue

            visited_cells[n] = true
            queue.append(n)

    return [] # TODO

```

Now, the path to get to the neighbor is the path to the current cell, plus the neighbor (and yes, we can just add `Array`s here):

```
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
    var queue := []
    queue.append(source)

    var visited_cells := {}
    visited_cells[source] = true

    var paths := {}
    paths[source] = [source]

    while queue.size() > 0:
        var current:Vector2 = queue.pop_front()
        if current == destination:
            return [] # TODO

        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            if visited_cells.has(n):
                continue

            visited_cells[n] = true
            paths[n] = paths[current] + [n]
            queue.append(n)

    return [] # TODO

```

And yes, we add to the queue…

Finally we return the path to the destination:

```
func bfs(maze:Array, source:Vector2, destination:Vector2) -> Array:
    var queue := []
    queue.append(source)

    var visited_cells := {}
    visited_cells[source] = true

    var paths := {}
    paths[source] = [source]

    while queue.size() > 0:
        var current:Vector2 = queue.pop_front()
        if current == destination:
            return paths[destination] # There is a path

        var neighbors = getNeighbors (current, maze)
        for n in neighbors:
            if visited_cells.has(n):
                continue

            visited_cells[n] = true
            paths[n] = paths[current] + [n]
            queue.append(n)

    return [] # There isn't a path

```

---

Please notice that Breadth-first search will find a path if there is a path, but it might not be the shortest one.

What I mention in the next few paragraphs is beyond this question, but I want to bring it up if you want to continue learning how these work:

If you want to make sure you get the shortest one, you want to implement Dijkstra's algorithm. The reason you don't see game developers talking about Dijkstra's algorithm as much is because it is exhaustive, in fact it compute the shortest path between all the points.

However we don't need to be exhaustive to get the shortest path between two points, we need a way to guess what parts to check… We get that from adding an heuristic. Which is what the famous A\* does.

It is also possible to further modify A\* to limit its memory use or some other constraints. Usually in exchange of losing the guarantee of getting the shortest path (instead we get a short enough path).

---

## Godot A\*

Alright, if you are using Godot, you can save yourself the trouble of implementing those algorithms and use the `AStar2D` class (there is also a 3D counterpart). They implements - as the name suggests - the A\* algorithm.

*However, you needed the lessons about using arrays and dictionaries we went over. Thus, I encourage you to - at least - go over the code I presented before.*

You can use the class `AStar2D` by adding cells with `add_point`. It requires ids. It is a good idea to be clever with the ids so you can compute the id for a given position. Something like this would work assuming the maze is rectangular:

```
var astar := AStar2D.new()
var height := maze.size()
var width := maze[0].size()
for j in height:
    for i in width:
        var id := j * width + i
        astar.add_point(id, Vector2(i, j))

```

Here the id is the number of the row multiplied by the length of the row (which gives you how many elements were before the start of the row) plus the position inside the row.

We, of course, don't need to add impasable points, so skip walls:

```
var astar := AStar2D.new()
var height := maze.size()
var width := maze[0].size()
for j in height:
    for i in width:
        if maze[j][i] == wall:
            continue

        var id := j * width + i
        astar.add_point(id, Vector2(i, j))

```

That also highlights that ids don't need to be continous. It is more important to be able to compute the id from the coordinates (which is why I didn't just have an id variable start at zero and increment it with each point).

You also want to connect them with `connect_points`. Which means we need to check the neighbors!

We are not going to connect to neighbors that has not been added. That includes:

* Positions outside the maze (we don't add those).
* Positions that are not passable (we don't add those).
* Positions that we haven't checked (when we check them we might add them).

In fact, we are not in a hurry to check positions ahead. When the loop gets to them, we can connect them (the connection is bidirectional by default). Thus, we can limit ourselves to position that we have already passed.

```
var astar := AStar2D.new()
var height := maze.size()
var width := maze[0].size()
for j in height:
    for i in width:
        if maze[j][i] == wall:
            continue

        var id := j * width + i
        astar.add_point(id, Vector2(i, j))
        for jn in [j - 1, j]:
            for i in [i - 1, i]:
                var idn := jn * width + in
                if astar.has_point(idn):
                    astar.connect_points(idn, id)

```

*I'll admit that the code above is a little too nested for my taste. If you see fit to refactor it by extracting functions, go ahead. In fact, you probably want to pass `astar` as a parameter because you will likely populate it once and query it multiple times.*

Ah, of course, you will query the `AStar`! Use `get_point_path`:

```
var path := astar.get_point_path(
    source.y * width + source.x,
    destination.y * width + destination.x
)

```

And there is your path. Guaranteed to be the shortest. And with good performance.

Be aware that it is computing the path you ask for (it does not compute all the paths in advance). *Thus, it is a good idea to hold on to the result while you are using it instead querying it every frame or something like that.*

---

## Wait… maze generation?

> The challenging part was to check if any paths exist in the maze, and to return them. If there are no solutions, generate another maze. However, I don't know how to do this yet.

You are checking if the maze is valid. There are maze generation algorithms that can guarantee to generate a valid maze.

---

You are generating by placing walls at random:

> I decided to generate each maze with specified width and height, then choose both the source and the destination cells, and finally randomly assign each cell to be either a space or a wall.

But you don't only know there isn't a path. You know, for each cell if there is a path.

Thus, instead of throwing away this maze, you could random-walk from the destination until it connects to one of the cells that has a path. Start by storing from where we are walking:

```
var walking := destination

```

The plan is to pick a neighbor at random. For this I'll declare a `RandomNumberGenerator`, and seed it with `randomize`:

```
var random := RandomNumberGenerator.new()
random.randomize()

```

Now compute the list of your possible neighbors:

```
var possible_neighbors := [
    Vector2(walking.x - 1, walking.y - 1),
    Vector2(walking.x, walking.y - 1),
    Vector2(walking.x + 1, walking.y - 1),

    Vector2(walking.x - 1, walking.y),
    Vector2(walking.x + 1, walking.y),

    Vector2(walking.x - 1, walking.y + 1),
    Vector2(walking.x, walking.y + 1),
    Vector2(walking.x + 1, walking.y + 1),
]

```

Make sure you aren't going outside the maze:

```
for index in range(possible_neighbors.size(), -1, -1, -1):
    var n:Vector2 = possible_neighbors[index]
    if n.x < 0.0 or n.x >= width or n.y < 0.0 or n.y >= height:
        possible_neighbors.remove_at(index)

```

Note that I'm iterating backwards to avoid re-indexing.

Now pick at random:

```
var neighbor := possible_neighbors[
    random.randi_range(0, possible_neighbors.size() - 1)
]

```

If it is a wall, carve it (I mean make it passable).

```
if maze[neighbor.y][neighbor.x] != wall:
    maze[neighbor.y][neighbor.x] = space # something like this?

```

If it was already passable, then check if there is a path from the `source` to it (if you are inside the `bfs` method you can check if `paths` has it as a key, if you are using `astar` ask it for a path to it). If there is a path, you are done.

Otherwise set `walking` to the `neighbor` and repeat. Until you find that there is a path.

**Addendum**: The random-walk is random™. Nothing prevents it from going over cells it already went over. So keeping a list of visited cells (similar to breath-first search) can allow you prevent that. Similarly, if you use a weighted random (look it up), you can make it more likely for it to pick a position that is closer to the source (by vector distance). And the closer is a cell to the source the more likely there is a path from to source to that cell (that, by the way, is an heuristic). This improvements will make the carving process go faster.

---

Be aware that I came up with this approach because:

* I'm keeping the same vein of what you were doing.
* I think there is plenty for you to learn from it.

However, you will likely get better results by picking an algorithm based on what you want for your game.
> 4 votes

---
Tags: algorithm, godot, gdscript, maze
---


title: Unity saving file on Android

text:
# Question
Title: Unity saving file on Android
I'm attempting to save player data into a `Saves` folder like so:

```
string relPath = "Saves/saveData.txt";
FileInfo file = new FileInfo(relPath);
file.Directory.Create();
// File.WriteAllText(relPath, JsonUtility.ToJson(data));

```

The issue I'm having is that `file.Directory.Create();` works on my PC (Windows 11) but not on my Android device. Am I missing something, maybe in build settings or maybe permissions on the device? Is there a better (i.e. more universal) option for creating a directory?

# Answer
It was a permission issue. Apparently the location the game files exist is readonly, so adding the Saves folder was giving an IOException. The simple solution is to move the saves to Application.persistentDataPath

```
string relPath = Application.persistentDataPath + "/Saves/saveData.txt";

```

If that doesn't work, look into this answer on how to setup `Application.logMessageReceived` so you can catch the general exception, which will offer an actual error message to look into.
> 1 votes

---
Tags: unity, android
---


# Question
Title: Bouncing ball with Euler integration loses speed over time
I am trying to implement free fall motion of a ball towards a plane.

I implemented collision detection and if collision happens, I change sign of velocity of a ball so it bounces off and climbs back up.

Now, it should climb back to its original position if there is no loss of energy, but after some testing I realized that after each bounce I have less speed than the bounce before.

Part of my code related to this:

```
if (collision)
{
    velocity.y = -velocity.y;

    std::cout << velocity.y << std::endl;
}

velocity.y += gravityAccel * ts.getSeconds();

position.x += velocity.x * ts.getSeconds() + ent.getComponent<RigidBody>().InitVelocity.x * ts.getSeconds();
position.y += velocity.y * ts.getSeconds() + ent.getComponent<RigidBody>().InitVelocity.y * ts.getSeconds();
position.z += velocity.z * ts.getSeconds() + ent.getComponent<RigidBody>().InitVelocity.z * ts.getSeconds();

```

I think that my problem lies in the calculations that happen right before ball reaches its maximum height. I think that he ball has some speed that is less than the speed change calculated by the next time step, so what I get is negative speed and reversal of motion direction along y axes a bit before it should actually happen. If this is so, I am trying to figure out the best way to solve this problem and have relatively nice free fall motion.

I know, you could say that this is not a bug but a feature since I have energy loss without asking for it. :)

# Answer
> 1 votes
You are using the velocity at the end of the interval to integrate the position (velocity updated before position). So position never reaches to the top. Every hop, it loses height.

You need to use the average velocity in the interval `ts.getSeconds()`

```
vi -> velocity at the end of previous update
vi+1 -> velocity at the end of current update
vi+1 = vi + a * dt;
(vi + vi+1) / 2.0 = (vi + (vi + a * dt)) / 2.0 = vi + 0.5 * a * dt

```

(assuming constant acceleration)

If you use that velocity when integrating the position, you will get

```
position += vi * dt + 0.5 * a * dt * dt    // use initial interval velocity i.e. update position before velocity

```

or

```
position += 0.5 * (vi + vi+1) * dt    // save velocity before updating it, and use both velocities to get the position

```

---
Tags: physics
---


# Question
Title: How to add text on screen using bitmapfont in libgdx?
I have a function class that implements `Screen` with a `bitmapFont` variable in it `BitmapFont f=new BitmapFont();`

In the render function of this class, I am trying to print the health of players t1 and t2.

```
    String s= "Player 1 Health\n"+t1.getHealth();
    game.getBatch().begin();
    // game.getBatch().draw("some other sprites)
    f.setColor(1.0f,1f,1f,1f);
    f.draw(game.getBatch(),s,300,1400);
    s= "Player 2 Health\n"+t2.getHealth();
    f.draw(game.getBatch(),s,1300,1400);
    game.getBatch().end()

```

However I am not able to see any output on my screeen. Please tell how to solve this one.

# Answer
This is work for me

```
        FreeTypeFontGenerator fontGenerator = new FreeTypeFontGenerator(Gdx.files.internal("font file"));
        FreeTypeFontGenerator.FreeTypeFontParameter fontParameter = new FreeTypeFontGenerator.FreeTypeFontParameter();

        fontParameter.size = 14;
        fontParameter.color = new Color(1, 1, 1, 1);

        BitmapFont font = fontGenerator.generateFont(fontParameter);
        font.draw(batch, "START GAME!", 0f, 0f + font.getCapHeight());

```
> 0 votes

---
Tags: libgdx
---


# Question
Title: Syncing & smoothing movement with rigidbodies with Socket.io
I am building a 2D top-down MMO that's very lightweight.

I have a master client that determines everything's position and actions, and sends this information to all other clients.

Now I have made a great deal of different solutions to the movement of my NPCs across the network, and some solutions are better than others, but none have been perfect. So I would love some feedback on this.

**Master client sends information to server:**

```
 void Start () {
    InvokeRepeating("CheckForMove", 1.0f, 1f);
 }

 void CheckForMove()
 {
    var distance = Vector3.Distance(lastPos, transform.position);
    if (distance > 0.02)  // Dont send information if movement is very small i.e bumping into a wall repeatedly etc
    {
        socket.Emit("enemyMove", Network.MobIdAndLocationToJson(gameObject.name, transform.position));
        moveEmit = true;
        lastPos = transform.position;
        spawnScript.spawnedEnemies[gameObject.name] = transform.position;
    }
}

```

**Server reveives the information:**

```
socket.on('enemyMove', function(data){

    // moves the monster that matches the given ID
    console.log('enemy is moving', data);

    socket.broadcast.emit('enemyMove', data);
});

```

**Player Clients receive the move information:**

```
private void OnEnemyMove(SocketIOEvent e)
{
        var position = new Vector3(e.data["x"].n, e.data["y"].n, -0.5f);
        var enemy = enemySpawner.FindEnemy(e.data["id"].str);
        var enemyNavigator = enemy.GetComponent<EnemyNavigator>();
        enemyNavigator.MoveThisEnemy(position);
}

```

Now the question becomes: what is the best way to go from here to smooth this movement as best I can?

The solutions I have tried are as follows:

**------------------ solution 1 ----------------------**

```
public void MoveThisEnemy(Vector3 position)
{
    anim.SetBool("walk", true);

    startTime = Time.time;
    DistanceToDest = Vector3.Distance(transform.position, position);

    destPos = position;
    isMoving = true;
}

```

and in update:

```
if (isMoving)
{
    if (currentTarget != null)
    {
        float currentDuration = Time.time - startTime;
        float journeyFraction = currentDuration / totalDistanceToDestination;
        transform.position = Vector3.Lerp(transform.position, destPos, journeyFraction);
    }
}

```

Although this works fine, the NPCs' movement is wonky: it finishes its movement faster than the next update can come no matter what, so despite lerping, it seems to move faster than I can provide it with updates. Imagine a cartoon slug that moves fast, stops, moves again, stops. So the NPC is always there and not just teleporting but still not the effect I am looking for.

**------------------ solution 2 ----------------------**

Here I simply try to just reproduce on the player client what I am doing on the master client but I make sure to correct the position of the NPC ever so often to guarantee its in the correct position.

```
public void MoveThisEnemy(Vector3 position)
{
    anim.SetBool("walk", true);
    transform.position = position;
    isMoving = true;
}

```

**and in update:**

```
if (isMoving)
{
    if (currentTarget != null)
    {
        var targetDistance = Vector3.Distance(transform.position, currentTarget.transform.position);

        if (targetDistance > minDist)
        {
            Vector3 direction = (currentTarget.transform.position - transform.position).normalized;
            rigid.MovePosition(transform.position + direction * speed * Time.deltaTime);
        }
    }
}

```

This is actually a very good solution as I can get the position correct with minimal amounts of data sent over the network. But since I have obstacles in my game, it gets very weird as moving the NPC's transform doesn't include collisions and it can perform weird movements when colliding. Furthermore, it seems to teleport to its position because of the `transform.position` updates when playing in full screen. But that's barely visible in smaller resolution for some reason.

I have also tried using `rigidbody.MovePosition` in the `MoveThisEnemy` function, but this just means it doesn't get updated correctly - it seems to be less precise than `transform.position`.

Any feedback would be greatly appreciated.

# Answer
> 0 votes
First of all, I might missunderstanded your question but it looks like your clients are updating the mobs position, this shouldn't happen. Game logic should be managed by the master server for several reasons from security (dont trust the client, ever) to math consistency (diferent platforms, different float precision)

About the smooth movement, a widely used approach is using movement prediction, checkpoints and interpolation.

## Movement prediction

If object A that is in P point moves in V direction at S speed, you know that, in 10 frames, that object A will be 10\*S units from P in V direction.

Knowing this, you can say from your server to your clients to move #12742 mob in (0.3, 1, 0.1) direction at speed 3 until point X is reached (f.e.), then, your clients can predict and update the position based on the server input.

## Checkpoints

Your mob moves dumbly for a given values from server, but if your server keep sending position and movement updates every server tick the client can update the position and the movement stuff with the correct one.

## Interpolation

This could lead to bumping, to fix it, you want to artificially lag a little the game and interpolate the position and movement between the last two recieved updates, by doing this and averaging with the last updates (and taking latency in mind) you can achieve smooth movement.

# Answer
> 0 votes
Your interpolation in solution 1 is completely wrong.

* You're dividing a time by a distance, which gets you a nonsensical value in units of seconds-per-meter, not appropriate to use as an interpolation blend factor.
* You're lerping from the current position to the destination, not from the start position. That gives you a Zeno's paradox-style ease-out movement, where you move x% of the distance one frame, then x% of the remainder the next, then x% of the remaining remainder...
* You're relying on absolute timestamps, which will function worse the longer your game is running.

This would be a more correct approach:

```
float progressSinceUpdate;
const float SERVER_UPDATES_PER_SECOND = 1f/INVOKE_REPEATING_DELAY;
Vector3 startPos;

public void MoveThisEnemy(Vector3 position)
{
    anim.SetBool("walk", true);

    profressSinceUpdate = 0f;

    startPos = transform.position;
    destPos = position;
    isMoving = true;
}

```

and in update:

```
if (isMoving)
{
    if (currentTarget != null)
    {
        progressSinceUpdate += Time.deltaTime * SERVER_UPDATES_PER_SECOND;

        if (progressSinceUpdate >= 1f) {
            progressSinceUpdate = 1f;
            isMoving = false;
        }

        transform.position = Vector3.Lerp(startPos, destPos, progressSinceUpdate);
    }
}

```

This will move in a straight line at a constant speed to reach the destination about the time that the next server update should arrive if the object is moving continuously.

Currently, if a packet is late, it will stop at its destination and wait. Alternatively, you can allow it to overshoot, assuming it will keep its current velocity, which can look smoother. That will require implementing an explicit "stop" signal so you can distinguish "next movement packet might just be late, keep moving" from "movement is finished".

---
Tags: unity, interpolation, synchronization, node.js, websocket
---


# Question
Title: Unity3D profiler isn't helping. How to debug increased memory?
Using Instruments or Xcode, my iOS game uses around 115 MB memory when the menu scene is loaded. After doing battles and other things within the game and reloading the menu, the memory usage is up to 170 MB.

The real problem is that Unity's profiler doesn't tell me anything: there are a few MB of extra system libraries and a few MB of extra Texture2D assets, but there's no explanation for the big increase. Adding more Resources.UnloadUnusedAssets() and GC.Collect() doesn't help.

How can I investigate this? (Note: it reaches a steady state. The memory doesn't continue to rise after a certain point.)

# Answer
Unity now has a first-party Memory Profiler tool which can perform before/after diffs of memory usage. You could use that to determine what in your game has allocated memory during periods of running.

See: https://docs.unity3d.com/Packages/com.unity.memoryprofiler@1.0/manual/index.html for instructions on how to install the profiler package and use the memory diff tool.
> 1 votes

# Answer
valgrind could help you detect memory leaks. I think there is an OSX version.
> -2 votes

---
Tags: unity
---


# Question
Title: Object not rotating properly towards Player
So i am trying to make a rope between player and where raycast hit in 2d godot.I have rope piece instance with rigibody/staticbody and pinjoint. So what i am doing is spawning enough pieces as a child of a gameobject between player and collision point of ray and the rope is spawning good enough but rotation isnt working. I have tried everything but its just not working.

Here is my horrendous code

```
elif Input.is_action_just_pressed("shoot") and ray.is_colliding():

    $".".gravity_scale=0
    var positionPlayer=$".".position

    var total = ceil(positionPlayer.distance_to(ray.get_collision_point()) / gap)

    var rays=ray.get_collision_point()

    var playerPos=$".".position

    isSpawned=true
    for n in total:

        if(firstTime):

            var pos=ray.get_collision_point()

            pos.y+=25
            pos.x-=35
            $"../ropewa".position=pos

            obj1=ray.get_collider()
            var rope=ropePiece.instance()
            $"../ropewa".add_child(rope)

            obj2=rope.get_node("PinJoint2D")
            obj2.node_a=obj1.get_path()
            obj2.node_b=rope.get_path()
            obj1=rope
            firstTime=false

        if(n==total-1):

            var rope=ropePiece.instance()
            $"../ropewa".add_child(rope)

            rope.position=obj1.position
            rope.position.y+=add

            obj2=rope.get_node("PinJoint2D")
            obj2.node_a=obj1.get_path()
            obj2.node_b=rope.get_path()
            $".".get_node("PinJoint2D").node_b=rope.get_path()

        else:
            if(firstTime==false):
                var rope=ropePiece.instance()
                $"../ropewa".add_child(rope)

                rope.position=obj1.position

                rope.position.y+=add

                obj2=rope.get_node("PinJoint2D")
                obj2.node_a=obj1.get_path()
                obj2.node_b=rope.get_path()
                obj1=rope

```

what I am doing is spawning a rope piece and joining the old rope piece and new rope piece. ropewa is the gameobject with all the child inside of it.$"." is the main player. My solution so far

# Answer
You have the position the raycast hit:

```
ray.get_collision_point()

```

That position is in global coordinates. Meanwhile the `position` of the player is not global (it is relative to its parent). Use `global_position` instead.

Let us do this:

```
var rope_start := ray.get_collision_point()
var rope_end := global_position

```

And we can figure out distance and direction:

```
var rope_length := rope_start.distance_to(rope_end)
var rope_direction := rope.start.direction_to(rope_end)

```

Define a size for the rope piece. I'll go with this (tweak it if it is wrong):

```
var rope_piece_length := 25.0 # gap

```

With that length and the direction we can have a vector that represents the step from once piece to the next:

```
var rope_piece_step := rope_piece_direction * rope_piece_length

```

Next figure out how many we need:

```
var rope_piece_count := int(ceil(rope_length / rope_piece_length))

```

Then we can iterate and figure out the position of each piece:

```
for n in rope_piece_count:
    var rope_piece_position := rope_start + rope_piece_step * n

```

Since you need to connect the pieces, you want to keep track of the prior piece you created to connect to it. In fact, since the first thing you will connect to is what the raycast collided with, we can initialize with that and avoid the first time check:

```
var rope_parent:Node = $"../ropewa"
var fixed:PhysicsBody2D = ray.get_collider()
for n in rope_segment_count:
    var rope_piece_position := rope_start + rope_piece_step * n
    var rope:PhysicsBody2D = ropePiece.instance()
    rope_parent.add_child(rope)
    rope.global_position = rope_piece_position
    var pin_joint := rope.get_node("PinJoint2D") as PinJoint2D
    pin_joint.node_a = fixed.get_path()
    pin_joint.node_b = rope.get_path()
    fixed = rope

```

I want to encourage you to compare my code with yours and see that it makes sense.

At the end (after the loop) you want to connect the last piece:

```
$PinJoint2D.node_b = fixed.get_path()

```

---

**On the `$` syntax**

There is no need to do this: `$"."`, because it is the same as `self`, but with overhead. So instead of `$".".position` you can write `self.position`.

In fact, *usually* you don't need `self`. If you are accessing one of the built-in properties feel free to simply use its name (e.g. `position` as opposed to `self.position`). *If you are accessing a custom property that was created with `setget`, then it depends (using `self` will trigger the `setget`, and not using it will bypass it).*

Also `$".".get_node("PinJoint2D")` is equivalent to `$"./PinJoint2D"`which is equivalent to `$"PinJoint2D"` which is equivalent to `$PinJoint2D` which is how I wrote it above.
> 1 votes

---
Tags: godot
---


# Question
Title: How do I make multiple circles bounce of each other
How will I calculate the direction of the circles when they hit each other? (there is no change in speed, there is no mass, and all circles have the same radius)

```
for (std::vector<Particle>::iterator i = particles.begin(); i != particles.end(); i++){
    for (std::vector<Particle>::iterator j = particles.begin(); j != particles.end(); j++){
        if (i != j){
            if (aabb.collides(i->getParticle()->getPosition(), j->getParticle()->getPosition(), i->getParticle()->getRadius(), j->getParticle()->getRadius())){

                j->setDirection(-j->getDirection());
                i->setDirection(-i->getDirection());
            }
        }
    }
    i->update(elapsedTime);
}

```

# Answer
I don't know C++ but here is an algorithm which I would try if want to solve this. The examples will be in JS but I will try too make code much easy to read as possible

What you should know about JS canvas and circle:

1. The point `(0, 0`) is the left upper corner of canvas
2. The positive direction of Ox is right
3. The positive direction of Oy is down
4. The coordinates of circle is the center of circle

Let's forget about many circles and think that we have only one circle in rectangle. We want circle to bounce from walls. We always know the center of circle and movement direction

* The red dot is touch point. Circle can touch line only in one point
* The green dot is center of circle
* The arrow in left is the previous movement direction
* The arrow in right is the next movement direction

We want to calculate the next direction. To calculate it we need to know that circle touches wall. But how to detect it if we know only position of the center of circle? For example we can track the 4 additional point on circle (topmost, bottommost, rightmost and leftmost points) and check if some of this point touches the wall. But it is not beautiful method for me and we know that in future we need to work with two (or more) circles which can touch each other not only in given 4 points. Adding more points is too complicated to calculating

Here is more efficient method: Instead of tracking the circle touching with wall we can track the touching center of circle and the touch with smaller rectangle. The smaller rectangle has offsets equal to radius of circle. When we touch the wall we can just reverse the direction of movement of circle depending on the wall that was touched. For example, if we touch the top or bottom wall, we only need to change the direction along Oy.

Let's code it:

```
const canvas = document.querySelector('#myCanvas');
const ctx = canvas.getContext('2d');

class Dot {
  x;
  y;

  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

class Vector {
  x;
  y;

  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

class Circle {
  center;
  radius;
  speed;
  direction;
  path2D;

  constructor(center, radius, speed, direction, color) {
    this.center = center;
    this.radius = radius;
    this.speed = speed;
    this.direction = direction;
    this.color = color;
  }

  draw() {
    this.path2D = new Path2D();
    this.path2D.arc(this.center.x, this.center.y, this.radius, 0, 2 * Math.PI);

    ctx.fillStyle = this.color;
    ctx.fill(this.path2D);
  }

  checkCollisionWithVerticalWalls() {
    const nextPositionX = this.center.x + this.direction.x;

    if (
        // CHECK IF CIRCLE TOUCHES RIGHT WALL OF SMALLER RECTANGLE
        nextPositionX > canvas.width - this.radius ||

        // CHECK IF CIRCLE TOUCHES LEFT WALL OF SMALLER RECTANGLE
        nextPositionX < this.radius
    ) {
      // REVERSE THE MOVEMENT DIRECTION BY Ox
      this.direction.x = -this.direction.x;
    }
  }

  checkCollisionWithHorizontalWalls() {
    const nextPositionY = this.center.y + this.direction.y;

    if (
        // CHECK IF CIRCLE TOUCHES TOP WALL OF SMALLER RECTANGLE
        nextPositionY > canvas.height - this.radius ||

        // CHECK IF CIRCLE TOUCHES BOTTOM WALL OF SMALLER RECTANGLE
        nextPositionY < this.radius
    ) {
      // REVERSE THE MOVEMENT DIRECTION BY Oy
      this.direction.y = -this.direction.y;
    }
  }

  move() {
    this.checkCollisionWithVerticalWalls();
    this.checkCollisionWithHorizontalWalls();

    this.center.x += this.direction.x * this.speed;
    this.center.y += this.direction.y * this.speed;
  }
}

const circle = new Circle(
  new Dot(canvas.width / 2, canvas.height / 2),
  16,
  2,
  new Vector(1, -1),
  'white'
);

function updateFrame() {
  // CLEAR CANVAS
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // DRAW CIRCLE
  circle.draw();

  // MOVE CIRCLE
  circle.move();
}

// DO NOT PAY ATTENTION TO THIS BELOW
// IT IS JUST CONFIGURING GAME LOOP
const targetFPS = 60;
const timeInterval = Math.floor(1000 / 60 * (60 / targetFPS));
let previousFrameTime = performance.now();

(function gameLoop(currentFrameTime = performance.now()) {

    requestAnimationFrame((timeStamp) => gameLoop(timeStamp));

    if (currentFrameTime - previousFrameTime < timeInterval) return;

    previousFrameTime = currentFrameTime;

    updateFrame();
})()
```

```
canvas {
  background: black;
}
```

```
<canvas id="myCanvas" width="480" height="320"></canvas>
```

This method works perfectly while the walls along the Ox or Oy. But what if the wall will be at a 45 degree angle? In this situation we can't just reverse the movement by Ox or Oy. In previous we understand how does touch detection principle work. Now let's talk about why if the walls along the Ox or Oy we can just reverse the movement

#### Some math theory:

1. The angle of incidence is equal to the angle of reflection
2. If we know the coordinates of incidence vector and the coordinates of surface normal then the coordinates of reflection vector can be calculated in this way

`b = a - 2 * (a, n) * n / (|n| ^ 2)`

`b` \- reflection vector

`a` \- incidence vector

`n` \- surface normal

`(a, n)` \- scalar product of incidence vector and surface normal

`|n|` \- length of surface normal

If we know the coordinates both of vectors (`a = (a_1, a_2), n = (n_1, n_2)`) then the scalar product we can be calculated in this way `(a, n) = a_1 * n_1 + a_2 * n_2`

In 2D the surface is a line so the normal is perpendicular to the direction vector of the line. To check if two vectors are perpendicular we can just calculate their scalar product and sure that it is `0`

If we don't know the coordinates of vector `x` but know the coordinates of its start point (`C = (c_1, c_2)`) and end point (`D = (d_1, d_2)`) then the coordinates of vector can be calculated in this way `x = (d_1 - c_1, d_2 - c_2)`

If we know the coordinates of vector then the length of vector can be calculated in this way `|n| = (n, n) ^ (1 / 2) = sqrt((n, n))`. But we need to calculate the square of length, so we will not need to calculate the square root of scalar product

The direction vector of Ox is `(0, 1)` so the normal (perpendicular vector) is `(1, 0)` because scalar product is `0 * 1 + 1 * 0 = 0`. Let's we have a movement direction vector `a = (a_1, a_2)` and our circle touches the one of horizontal wall. Let's calculate the vector `b`:

`b = a - 2 * (a, n) * n / (|n| ^ 2) =`

`= (a_1, a_2) - 2 * ((a_1, a_2), (n_1, n_2)) * (n_1, n_2) / (sqrt(((n_1, n_2), (n_1, n_2))) ^ 2) =`

we know the coordinates of vector `n` it is `(0, 1)`

`= (a_1, a_2) - 2 * ((a_1, a_2), (0, 1)) * (0, 1) / ((0, 1), (0, 1)) =`

`= (a_1, a_2) - 2 * (a_1 * 0 + a_2 * 1) * (0, 1) / (0 * 0 + 1 * 1) =`

`= (a_1, a_2) - 2 * a_2 * (0, 1) / 1 =`

`= (a_1, a_2) - (0, 2 * a_2) =`

`= (a_1 - 0, a_2 - 2 * a_2) =`

`= (a_1, -a_2)`

Let's recap:

* The vector `a = (a_1, a_2)`
* The vector `b = (a_1, -a_2)`
* With the same calculations we can prove that if our circle touches the one of horizontal wall then the vector `b` will be `(-a_1, a_2)`

Let's code it:

```
const canvas = document.querySelector('#myCanvas');
const ctx = canvas.getContext('2d');

class Dot {
  x;
  y;

  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

class Vector {
  x;
  y;

  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

class MyMath {
  static scaleVector(vector, scale) {
    return new Vector(vector.x * scale, vector.y * scale);
  }

  static sumOfVectors(vector1, vector2) {
    return new Vector(vector1.x + vector2.x, vector1.y + vector2.y);
  }

  static diffOfVectors(vector1, vector2) {
    return MyMath.sumOfVectors(vector1, MyMath.scaleVector(vector2, -1));
  }

  static scalarProduct(vector1, vector2) {
    return vector1.x * vector2.x + vector1.y * vector2.y;
  }

  static reflectionVector(normal, incidenceVector) {
    const scalarProduct = MyMath.scalarProduct(normal, incidenceVector);
    const dividendVector = MyMath.scaleVector(normal, 2 * scalarProduct);
    const divisor = MyMath.scalarProduct(normal, normal);
    const subtrahendVector = MyMath.scaleVector(dividendVector, 1 / divisor);

    return MyMath.diffOfVectors(incidenceVector, subtrahendVector);
  }
}

class Circle {
  center;
  radius;
  speed;
  directionVector;
  path2D;

  constructor(center, radius, speed, directionVector, color) {
    this.center = center;
    this.radius = radius;
    this.speed = speed;
    this.directionVector = directionVector;
    this.color = color;
  }

  draw() {
    this.path2D = new Path2D();
    this.path2D.arc(this.center.x, this.center.y, this.radius, 0, 2 * Math.PI);

    ctx.fillStyle = this.color;
    ctx.fill(this.path2D);
  }

  checkCollisionWithVerticalWalls() {
    const nextPositionX = this.center.x + this.directionVector.x;

    if (
        // CHECK IF CIRCLE TOUCHES RIGHT WALL OF SMALLER RECTANGLE
        nextPositionX > canvas.width - this.radius ||

        // CHECK IF CIRCLE TOUCHES LEFT WALL OF SMALLER RECTANGLE
        nextPositionX < this.radius
    ) {
      // REVERSE THE MOVEMENT DIRECTION BY Ox
      this.directionVector = MyMath.reflectionVector(new Vector(1, 0), this.directionVector);
    }
  }

  checkCollisionWithHorizontalWalls() {
    const nextPositionY = this.center.y + this.directionVector.y;

    if (
        // CHECK IF CIRCLE TOUCHES TOP WALL OF SMALLER RECTANGLE
        nextPositionY > canvas.height - this.radius ||

        // CHECK IF CIRCLE TOUCHES BOTTOM WALL OF SMALLER RECTANGLE
        nextPositionY < this.radius
    ) {
      // REVERSE THE MOVEMENT DIRECTION BY Oy
      this.directionVector = MyMath.reflectionVector(new Vector(0, 1), this.directionVector);
    }
  }

  move() {
    this.checkCollisionWithVerticalWalls();
    this.checkCollisionWithHorizontalWalls();

    this.center.x += this.directionVector.x * this.speed;
    this.center.y += this.directionVector.y * this.speed;
  }
}

const circle = new Circle(
  new Dot(canvas.width / 2, canvas.height / 2),
  16,
  2,
  new Vector(1, -1),
  'white'
);

function updateFrame() {
  // CLEAR CANVAS
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // DRAW CIRCLE
  circle.draw();

  // MOVE CIRCLE
  circle.move();
}

// DO NOT PAY ATTENTION TO THIS BELOW
// IT IS JUST CONFIGURING GAME LOOP
const targetFPS = 60;
const timeInterval = Math.floor(1000 / 60 * (60 / targetFPS));
let previousFrameTime = performance.now();

(function gameLoop(currentFrameTime = performance.now()) {

    requestAnimationFrame((timeStamp) => gameLoop(timeStamp));

    if (currentFrameTime - previousFrameTime < timeInterval) return;

    previousFrameTime = currentFrameTime;

    updateFrame();
})();
```

```
canvas {
  background: black;
}
```

```
<canvas id="myCanvas" width="480" height="320"></canvas>
```

Now we have almost everything we need to solve the main problem. The problems are that we don't have any wall between circles when they touch each other, we don't know the normal of this wall and we must know when two circles are touching each other

#### Some math theory:

1. Two circles are touching each other if the distance between their centers are equal (or less) to sum of their radii
2. Two circles can touch each other only in one point

1.1. To find this point we must know the coordinates of centers of circles and their radii

1.2. Calculate the ratio of two radii
3. If we draw a radius from center of any circle to this point then the radius will be perpendicular to the wall

We know the coordinates of each circle, we also know their radii and because of the radius is perpendicular we can use it as normal to wall. Notice that if we already have normal to wall we don't need in wall itself

#### Some math theory:

Let's we have two points `A(a_1, a_2)` and `B(b_1, b_2)` and we must find the point `M (m_1, m_2)` between these two points which divide segment in given ratio `R = AM / BM` where the `AM` \- is length of `AM` segment and the `BM` \- is length of `BM` segment. In general terms, the formula looks like this:

* `m_1 = (a_1 + R * b_1) / (1 + R)`
* `m_2 = (a_2 + R * b_2) / (1 + R)`

If the ratio is equal to `BM / AM` then the formula looks like this:

* `m_1 = (b_1 + R * a_1) / (1 + R)`
* `m_2 = (b_2 + R * a_2) / (1 + R)`

We have same problem but in our situation the centers of circles are the edge points of segment and the ratio is equal to `r_1 / r_2`. We also have condition that all circles have same radii so the ratio will be equal to `1`. Then formula for us will look like this:

* `m_1 = (a_1 + 1 * b_1) / (1 + 1) = (a_1 + b_1) / 2`
* `m_2 = (a_2 + 1 * b_2) / (1 + 1) = (a_2 + b_2) / 2`

Now we know everything to solve the main problem

Let's code it:

```
const canvas = document.querySelector('#myCanvas');
const ctx = canvas.getContext('2d');

class Dot {
  x;
  y;

  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

class Vector {
  x;
  y;

  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

class MyMath {
  static distance (dot1, dot2) {
    return Math.sqrt((dot1.x - dot2.x) ** 2 + (dot1.y - dot2.y) ** 2);
  }

  static vectorFromTwoDots(dot1, dot2) {
    return new Vector(dot2.x - dot1.x, dot2.y - dot1.y);
  }

  static scaleVector(vector, scale) {
    return new Vector(vector.x * scale, vector.y * scale);
  }

  static sumOfVectors(vector1, vector2) {
    return new Vector(vector1.x + vector2.x, vector1.y + vector2.y);
  }

  static diffOfVectors(vector1, vector2) {
    return MyMath.sumOfVectors(vector1, MyMath.scaleVector(vector2, -1));
  }

  static scalarProduct(vector1, vector2) {
    return vector1.x * vector2.x + vector1.y * vector2.y;
  }

  static reflectionVector(normal, incidenceVector) {
    const scalarProduct = MyMath.scalarProduct(normal, incidenceVector);
    const dividendVector = MyMath.scaleVector(normal, 2 * scalarProduct);
    const divisor = MyMath.scalarProduct(normal, normal);
    const subtrahendVector = MyMath.scaleVector(dividendVector, 1 / divisor);

    return MyMath.diffOfVectors(incidenceVector, subtrahendVector);
  }
}

class Circle {
  center;
  radius;
  speed;
  directionVector;
  path2D;

  constructor(center, radius, speed, directionVector, color) {
    this.center = center;
    this.radius = radius;
    this.speed = speed;
    this.directionVector = directionVector;
    this.color = color;
  }

  draw() {
    this.path2D = new Path2D();
    this.path2D.arc(this.center.x, this.center.y, this.radius, 0, 2 * Math.PI);

    ctx.fillStyle = this.color;
    ctx.fill(this.path2D);
  }

  checkCollisionWithVerticalWalls() {
    const nextPositionX = this.center.x + this.directionVector.x;

    if (
      // CHECK IF CIRCLE TOUCHES RIGHT WALL OF SMALLER RECTANGLE
      nextPositionX > canvas.width - this.radius ||

      // CHECK IF CIRCLE TOUCHES LEFT WALL OF SMALLER RECTANGLE
      nextPositionX < this.radius
    ) {
      // REVERSE THE MOVEMENT DIRECTION BY Ox
      this.directionVector = MyMath.reflectionVector(new Vector(1, 0), this.directionVector);
    }
  }

  checkCollisionWithHorizontalWalls() {
    const nextPositionY = this.center.y + this.directionVector.y;

    if (
      // CHECK IF CIRCLE TOUCHES TOP WALL OF SMALLER RECTANGLE
      nextPositionY > canvas.height - this.radius ||

      // CHECK IF CIRCLE TOUCHES BOTTOM WALL OF SMALLER RECTANGLE
      nextPositionY < this.radius
    ) {
      // REVERSE THE MOVEMENT DIRECTION BY Oy
      this.directionVector = MyMath.reflectionVector(new Vector(0, 1), this.directionVector);
    }
  }

  checkCollisionWithCircle(circle) {
    const distanceBetweenCenters = MyMath.distance(this.center, circle.center);
    const sumOfRadii = this.radius + circle.radius;

    if (distanceBetweenCenters > sumOfRadii) return;

    const touchPoint = new Dot(
      (this.center.x + circle.center.x) / 2,
      (this.center.y + circle.center.y) / 2,
    );

    const normal = MyMath.vectorFromTwoDots(touchPoint, this.center);

    this.directionVector = MyMath.reflectionVector(normal, this.directionVector);
    circle.directionVector = MyMath.reflectionVector(normal, circle.directionVector);
  }

  move() {
    this.checkCollisionWithVerticalWalls();
    this.checkCollisionWithHorizontalWalls();

    this.center.x += this.directionVector.x * this.speed;
    this.center.y += this.directionVector.y * this.speed;
  }
}

const radius = 16;
const speed = 2;

const circles = [
  new Circle(
    new Dot(canvas.width / 2 - 30, canvas.height / 2 - 30),
    radius,
    speed,
    new Vector(-1, -1),
    'red'
  ),
  new Circle(
    new Dot(canvas.width / 2 - 30, canvas.height / 2 + 30),
    radius,
    speed,
    new Vector(-1, 1),
    'green'
  ),
  new Circle(
    new Dot(canvas.width / 2 + 30, canvas.height / 2 - 30),
    radius,
    speed,
    new Vector(1, -1),
    'blue'
  ),
  new Circle(
    new Dot(canvas.width / 2 + 30, canvas.height / 2 + 30),
    radius,
    speed,
    new Vector(1, 1),
    'yellow'
  )
];

function updateFrame() {
  // CLEAR CANVAS
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // DRAW CIRCLE
  for (let i = 0; i < circles.length; ++i) {
    circles[i].draw();
  }

  // MOVE CIRCLE
  for (let i = 0; i < circles.length; ++i) {
    circles[i].move();
  }

  // CHECK COLLISION WITH OTHER CIRCLES
  for (let i = 0; i < circles.length; ++i) {
    for (let j = i + 1; j < circles.length; ++j) {
      circles[i].checkCollisionWithCircle(circles[j]);
    }
  }
}

// DO NOT PAY ATTENTION TO THIS BELOW
// IT IS JUST CONFIGURING GAME LOOP
const targetFPS = 60;
const timeInterval = Math.floor(1000 / 60 * (60 / targetFPS));
let previousFrameTime = performance.now();

(function gameLoop(currentFrameTime = performance.now()) {

  requestAnimationFrame((timeStamp) => gameLoop(timeStamp));

  if (currentFrameTime - previousFrameTime < timeInterval) return;

  previousFrameTime = currentFrameTime;

  updateFrame();
})();
```

```
canvas {
  background: black;
}
```

```
<canvas id="myCanvas" width="480" height="320"></canvas>
```

## P.S.

Perhaps there are more optimal methods / algorithms for solving this problem, but I would do this

## P.P.S.

Feel free to ask any questions about code or algorithm
> 2 votes

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


title: Bounding box rotated on import

text:
# Question
Title: Bounding box rotated on import
For some reason my bounding box is always tilted when i import to unity. I've checked for loose geometry and everything but there's nothing.

# Answer
I know this is not a new post but I found myself with the same problem. This situation happens when the hip bone is rotated so, you need to set it vertically. Hope it helps.
> 1 votes

# Answer
If you are using armature, check if you have your root bone named Root, so SkinnedMeshRenderer knows what bone to use.

Note that after renaming your bone, your possible blender animations might be broken. To fix this issue follow the instructions here

https://blenderartists.org/t/tip-fix-for-when-you-rename-a-bone-while-its-animations-retain-the-old-name/1367948
> 1 votes

# Answer
Looks like you're using Blender. In Blender, make sure that the object has its rotation and scale applied to the mesh. In object mode, select the object, hit `Ctrl + A`, apply rotation and scale.

While the mesh itself may look fine in Blender, the object that holds the mesh might be rotated or scaled. Blender will export the unscaled and unrotated mesh directly from saved mesh data without the object's rotation and scale applied.
> 0 votes

# Answer
I found the answer, for some reason disabling "Update when offscreen" fixed the issue, no idea why.
> 0 votes

---
Tags: unity, blender, bounding-boxes, import
---


# Question
Title: Color mismatch between transparent asset from Photoshop and Unity in 3D project
I have created a simple asset in photoshop (teal square) with transparency. To make the square semi-transparent, I just changed the layer opacity from 100% --\> 50%, then exported the file as a .png.

In unity, I boot up a base 2D project and import the .png. I create a white canvas and place an image over the UI canvas with the teal square as the image. The color is identical to the photoshop image on a white background.

But when I do the same in 3D project, the image has a slightly different (lighter) color. Below are screengrabs of each of the images. Clearly the 3D project image is a lot different than the other two, and this has been really frustrating for setting up my UI in my 3D project. Additionally, the inspector settings are identical for the sprite in the 2D and 3D projects. Anybody know what's going on?

**Inspector**

**3D project**

**2D project**

**Photoshop**

# Answer
> 1 votes
Finally figured this out. In 3D unity projects, the default color space setting is "Linear" while in 2D projects it is "Gamma". You can change this setting by going into Project Settings \> Player \> Color Space.

I'll also add that from reading a bit, "Linear" is the preferred color space for 3D projects because it is much more optimized than Gamma. In the end, I'm just going to live with this difference in UI color from Photoshop, save all of my assets without any transparency, and change the transparency of my UI in unity rather than baking it in for photoshop.

There are apparently more complex solutions where you can render particular elements (i.e. UI elements) in Gamma rather than Linear, but it involves quite a bit of messing around and writing your own script/package to properly achieve this.

---
Tags: unity, 3d, sprites, color
---


# Question
Title: Finding a point on the edge of a circle from a point offset from its centre in a certain direction
How would I find the point on the edge of a circle (the green point on the diagram below) in a certain direction (indicated by the arrow) from a point inside of the circle (the red point) in Unity? I know the start point inside the circle, the circles circumference and the direction however I'm at a loss on how to calculate this (trigonometry is not my strong suit).

# Answer
Here is the general method you will want to use.

Here, I assume that the circle center is at coordinate $$(x\_0, y\_0)$$ the red point is at coordinate $$(x\_1, y\_1)$$ and your final coordinate is given by $$(x\_f, y\_f)$$

Also note that the angle $$\theta$$ can be found by finding the angle between the unit vector in the given direction and the unit vector in the y-direction (0, 1).

Solve these systems of equations to get your desired final coordinates

As an example say the circle is centered at (0, 0), and our directional vector is in the +y direction as you've shown in your example (0, 1). Then theta = 0, costheta = 1 and sintheta = 0. Solving we get:

$$x\_f = x\_1$$ $$y\_f = y\_1 + ((x\_f - x\_1)^2 + (y\_f - y\_1)^2)^{1/2}$$ $$x\_f^2 + y\_f^2 = r^2$$

Subbing in for y\_f we get

$$y\_f^2 = r^2 - x\_1^2$$

Thus your final position in terms of the radius and position of the red point is $$x\_f = x\_1$$ $$y\_f = \sqrt{r^2 - x\_1^2}$$
> 1 votes

---
Tags: unity
---


# Question
Title: How to modify single-scene ECS setup to support multiple local players in different scenes?
I'm currently developing a game in Monogame / C#. I have the underlying game engine set up in the following way:

* Entity/Component/System architecture
* A Scene includes a map, cameras, and a list of entities
* Systems act on the top scene in a scene stack each frame

The above approach is serving me well, but I want the engine to be able to cope with local multiplayer games in the future. Currently, the above architecture can cope with multiple players, as long as they are always in the same scene (due to the 1:1 scene/map relationship).

My question is a general one -- what changes would I need to make to facilitate multiple local players who can move between scenes independently? My initial thought is that I'd need to decouple scenes from game screens, but am having trouble visualising the relationship between scenes and cameras/entities/scene transitions/etc. in this scenario.

# Answer
You would need one complete scene stack per player.

Any shared data would have to be moved either outside of, or to the root of the ECS.

In general, I do not recommend the formal ECS methodology for application under MonoGame.

Much of ECS is superseded by good C# class design, in terms of readability, coding efficiency, and speed.
> 0 votes

---
Tags: c#, multiplayer, monogame, scene, entity-component-system
---


# Question
Title: Finding the center of rotation in 3d knowing the start/end transformations
I need your help to solve a trigonometry problem, I'm unable to find any documentation about on the web...

For convenience, I will use "transform" to indicate a position+orientation.

Let's say that we have a general shape (the green box) and we apply to it a displacement and a rotation to obtain the blue box (the grey box represents a possible interpolation between the initial and the final transform)

Now, suppose that the transform we apply produce this result. To match the blue box transformation we could simply apply a rotation to the green box with the center represented by the orange dot.

The question is the following: Is it possible to compute the center of rotation for any generic case knowing only the transformations of the green and the blue box? Ex:

Why this need? Consider the image n2, if I simply interpolate \[0,5\] the transformation of the green and the blue box I obtain the grey box of the image n1, what I'm looking for is a way to obtain the grey box of the image n2.

Thank you so much!

# Answer
I'm afraid it's not quite possible, simply because there is always more than one solution. For example, even if we know the rotation center, you can get the same final pose by rotating in different ways:

But even using different points as rotation center can work as well:

So, in order to automate this process, you would have to introduce additional constraints (like, for example, fix the direction in which you want to rotate). The specifics of how to solve it then would depend on which constraints you choose and how you define the positions and orientations.
> 0 votes

---
Tags: rotation, transformation, trigonometry, orientation
---


# Question
Title: LedgeClimb script not choosing point to grab correctly when encountering Stacked meshes (meshes on top of one another)?
I created a script to climb ledges. It shoots 4 raycasts total:

-2 shooting straight forward from player (origins left and right of player)

-2 shooting down from forward&above player (origins left and right of player)

Like so:

If these all hit, it calculates the midpoint of the Upper Raycasts to determine what Vector3 position to AddForce towards. This Vector3 is called `targetPointToJumpTo`.

This ledge grabbing technique seems to work well enough in most cases. However, when it encounters a situation of meshes stacked on top of each other, it returns `targetPointToJumpTo` as a point between those meshes, as in inside of them where there isn't actually a ledge.

Screenshot of problem:

I'm quite confused as to the cause of this behavior. Would anyone be able to assess possible solutions? Below is my full ledgegrab script.

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

public class LedgeGrab : MonoBehaviour
{
    public LayerMask layerMask;

    //lower raycasts
    public float offsetRight;
    public float offsetLeft;
    public float offsetUp;
    public float raycastLength;

    //upper raycasts
    public RaycastHit upleftRayHit;
    public RaycastHit uprightRayHit;
    public float upraycastLength;

    //empty game objects that upper raycasts spawn from
    public Transform upperLeftTransform;
    public Transform upperRightTransform;

    //misc
    PlayerControllerScript sf1;
    [SerializeField] private float angleBetweenRaycasts = 0f;
    public float distanceToGrabLedge;
    public bool jumpingToLedge;
    public bool holdingOnToLedge;
    [SerializeField] Vector3 targetPointToJumpTo;
    [SerializeField] float timeSinceLastOnLedge = 0;

    private void Awake()
    {
        sf1 = GetComponent<PlayerControllerScript>();
    }
    private void Update()
    {

        if (timeSinceLastOnLedge > 1 &&
            holdingOnToLedge == false
            && angleBetweenRaycasts != 0
            && Vector3.Distance(transform.position, MidPoint(uprightRayHit.point, upleftRayHit.point)) < distanceToGrabLedge)
        {
            timeSinceLastOnLedge = 0;
            //print("Grab");
            targetPointToJumpTo = MidPoint(uprightRayHit.point, upleftRayHit.point);
            jumpingToLedge = true;
        }

        if (Input.GetKeyDown(KeyCode.X)
            && holdingOnToLedge == true)
        {
            //print("Release");
            holdingOnToLedge = false;
            sf1.r.useGravity = true;
            sf1.r.velocity = sf1.r.velocity;
            sf1.ignoreInput = false;
        }
    }

    private void FixedUpdate()
    {
        LowCasts();
        UpCasts();
        angleBetweenRaycasts = Vector3.Angle(upleftRayHit.point, uprightRayHit.point);

        if(jumpingToLedge == true)
        {
            //addforce towards targetPointToJumpTo every frame
            sf1.r.AddForce(targetPointToJumpTo - transform.position);

            //if reached close enough to point
            if (Vector3.Distance(transform.position, targetPointToJumpTo) < 1.5)
            {
                jumpingToLedge = false;
                sf1.ignoreInput = true;
                holdingOnToLedge = true;
            }
        }

        if (holdingOnToLedge == true)
        {
            sf1.r.useGravity = false;
            sf1.r.velocity = Vector3.zero;
        }
        else
        {
            timeSinceLastOnLedge = timeSinceLastOnLedge + 1 * Time.deltaTime;
        }
    }

    void LowCasts()
    {

        RaycastHit hit;

        //Right Raycast
        if (Physics.Raycast(transform.position + transform.right * offsetRight + transform.up * offsetUp, transform.TransformDirection(Vector3.forward), out hit, raycastLength, layerMask))
        {
            //Debug.Log("Right Did Hit");
        }
        else
        {
            //Debug.Log("Right Did not Hit");
        }

        //Left Raycast
        if (Physics.Raycast(transform.position - transform.right * offsetLeft + transform.up * offsetUp, transform.TransformDirection(Vector3.forward), out hit, raycastLength, layerMask))
        {
            //Debug.Log("Left Did Hit");
        }
        else
        {
            //Debug.Log("Left Did not Hit");
        }
    }

    void UpCasts()
    {

        //UpperLeft Raycast
        if (Physics.Raycast(upperLeftTransform.position, transform.TransformDirection(Vector3.down), out upleftRayHit, upraycastLength, layerMask))
        {
        }
        else
        {
            //print("Didnt hit");
        }

        //UpperRight Raycast
        if (Physics.Raycast(upperRightTransform.position, transform.TransformDirection(Vector3.down), out uprightRayHit, upraycastLength, layerMask))
        {
        }
        else
        {
        }
    }

    public static Vector3 MidPoint(Vector3 start, Vector3 end)
    {
        return new Vector3(
            (start.x + end.x) / 2,
            (start.y + end.y) / 2,
            (start.z + end.z) / 2
        );
    }

}

```

Please note the actual Jump method is in `PlayerControllerScript`. This script though is what Adds Force to Player rigidbody towards viable ledges. Theoretically player does not even need to jump to grab onto ledge with this current code.

Thank you for any insight here.

# Answer
The problem was that if you have a Raycast that originates within a Mesh, then there is basically no way to detect the backfaces, even if you have `queriesHitBackfaces` on.

From the Unity documentation:

`Raycasts will not detect Colliders for which the Raycast origin is inside the Collider`

Therefore, what I ended up doing was a different approach: Detecting if there was room above the ledge via a CapsuleCast. Now when two meshes are stacked on each other, CapsuleCast notices and flags the ledge grab as non-viable.
> 1 votes

---
Tags: unity, rigidbody
---


# Question
Title: How to improve performance of code for finding climbing annotations?
The goal is to be able to climb any ledge, even if the ledge is an odd shape. Therefore, I found a script that searches for viable "climb holds" along any mesh of any shape. You can then use these as points for your character to grab on to and shimmy along.

This is that script:

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

[ExecuteInEditMode]
public class anchorpoints : MonoBehaviour
{
    protected struct Triangle
    {
        public Vector3 v1;

        public Vector3 v2;

        public Vector3 v3;

        public int index;
    }

    protected struct SharedEdge
    {
        public Vector3 v1;

        public Vector3 v2;
    }

    protected struct TrianglePair
    {
        public Triangle t1;

        public Triangle t2;

        public SharedEdge e;
    }

    private const float UP_THRESHOLD = 60f;

    private const float MIN_DIFF = 60f;

    private const float MAX_DIFF = 120f;

    private const float MIN_HH_DIST = 0.2f;

    private const float MIN_TRIANGLE_AREA = 0.1f;

    private const bool DEBUG = false;

    private const bool FULL_HOLD_PASS = false;

    private List<TrianglePair> trianglePairs;

    private Mesh mesh;

    private int[] triangles;

    private Vector3[] vertices;

    private Vector3[] normals;

    private Transform tr;

    private GameObject activeGameObject;

    private void Start()
    {
        Transform[] componentsInChildren = GetComponentsInChildren<Transform>();
        activeGameObject = base.gameObject;
        if (componentsInChildren.Length != 0)
        {
            for (int i = 0; i < componentsInChildren.Length; i++)
            {
                GameObject gameObject = componentsInChildren[i].gameObject;
                if (!gameObject.activeInHierarchy)
                {
                    continue;
                }
                activeGameObject = gameObject;
                tr = gameObject.transform;
                gameObject.tag = "Climbable";
                trianglePairs = new List<TrianglePair>();
                MeshFilter component = gameObject.GetComponent<MeshFilter>();
                if (!(component == null))
                {
                    mesh = component.sharedMesh;
                    triangles = mesh.triangles;
                    vertices = mesh.vertices;
                    normals = mesh.normals;
                    PopulateTrianglePairs();
                    if (trianglePairs.Count > 0)
                    {
                        CrawlMeshForHandholds();
                    }
                }
            }
        }
        else
        {
            tr = base.gameObject.transform;
            base.gameObject.tag = "Climbable";
            trianglePairs = new List<TrianglePair>();
            MeshFilter component2 = base.gameObject.GetComponent<MeshFilter>();
            mesh = component2.sharedMesh;
            triangles = mesh.triangles;
            vertices = mesh.vertices;
            normals = mesh.normals;
            PopulateTrianglePairs();
            if (trianglePairs.Count > 0)
            {
                CrawlMeshForHandholds();
            }
        }
        UnityEngine.Object.DestroyImmediate(this);
    }

    private void PopulateTrianglePairs()
    {
        for (int i = 0; i < triangles.Length; i += 3)
        {
            Vector3 v = tr.TransformPoint(vertices[triangles[i]]);
            Vector3 v2 = tr.TransformPoint(vertices[triangles[i + 1]]);
            Vector3 v3 = tr.TransformPoint(vertices[triangles[i + 2]]);
            int num = 0;
            int num2 = i - 3;
            int num3 = i + 3;
            while ((num2 > 0 || num3 < triangles.Length) && num < 3)
            {
                if (num2 > 0)
                {
                    Vector3 vector = tr.TransformPoint(vertices[triangles[num2]]);
                    Vector3 vector2 = tr.TransformPoint(vertices[triangles[num2 + 1]]);
                    Vector3 vector3 = tr.TransformPoint(vertices[triangles[num2 + 2]]);
                    if (FindSharedEdge(v, v2, v3, vector, vector2, vector3, out SharedEdge e))
                    {
                        num++;
                        Triangle t = default(Triangle);
                        t.v1 = v;
                        t.v2 = v2;
                        t.v3 = v3;
                        t.index = i;
                        Triangle t2 = default(Triangle);
                        t2.v1 = vector;
                        t2.v2 = vector2;
                        t2.v3 = vector3;
                        t2.index = num2;
                        if (!TrianglePairsContains(t, t2))
                        {
                            TrianglePair item = default(TrianglePair);
                            item.t1 = t;
                            item.t2 = t2;
                            item.e = e;
                            trianglePairs.Add(item);
                        }
                    }
                    num2 -= 3;
                }
                if (num3 >= triangles.Length)
                {
                    continue;
                }
                Vector3 vector4 = tr.TransformPoint(vertices[triangles[num3]]);
                Vector3 vector5 = tr.TransformPoint(vertices[triangles[num3 + 1]]);
                Vector3 vector6 = tr.TransformPoint(vertices[triangles[num3 + 2]]);
                if (FindSharedEdge(v, v2, v3, vector4, vector5, vector6, out SharedEdge e2))
                {
                    num++;
                    Triangle t3 = default(Triangle);
                    t3.v1 = v;
                    t3.v2 = v2;
                    t3.v3 = v3;
                    t3.index = i;
                    Triangle t4 = default(Triangle);
                    t4.v1 = vector4;
                    t4.v2 = vector5;
                    t4.v3 = vector6;
                    t4.index = num3;
                    if (!TrianglePairsContains(t3, t4))
                    {
                        TrianglePair item2 = default(TrianglePair);
                        item2.t1 = t3;
                        item2.t2 = t4;
                        item2.e = e2;
                        trianglePairs.Add(item2);
                    }
                }
                num3 += 3;
            }
        }
    }

    private void CrawlMeshForHandholds()
    {
        for (int i = 0; i < trianglePairs.Count; i++)
        {
            TrianglePair trianglePair = trianglePairs[i];
            Vector3 normal = GetNormal(trianglePair.t1);
            Vector3 normal2 = GetNormal(trianglePair.t2);
            Triangle triangle = trianglePair.t1;
            Triangle triangle2 = trianglePair.t2;
            float num = Vector3.Dot(Vector3.up, normal);
            float num2 = Vector3.Dot(Vector3.up, normal2);
            Vector3 vector;
            Vector3 vector2;
            if (num > num2)
            {
                vector = normal;
                vector2 = normal2;
            }
            else
            {
                vector = normal2;
                vector2 = normal;
                triangle = trianglePair.t2;
                triangle2 = trianglePair.t1;
            }
            if (!(Vector3.Angle(Vector3.up, vector) > 60f) && !(Vector3.Angle(vector, vector2) < 60f) && !(Vector3.Angle(vector, vector2) > 120f))
            {
                float y = ((triangle.v1 + triangle.v2 + triangle.v3) / 3f).y;
                if (!(((triangle2.v1 + triangle2.v2 + triangle2.v3) / 3f).y > y))
                {
                    AddHandholds(trianglePair.e, vector, vector2);
                }
            }
        }
    }

    private void AddHandholds(SharedEdge e, Vector3 up, Vector3 fn)
    {
        Vector3 vector = e.v2 - e.v1;
        if (vector.magnitude < 0.2f)
        {
            GameObject gameObject = AddHold(e.v1, up, fn, activeGameObject.transform);
            AddHold(e.v2, up, fn, gameObject.transform);
            return;
        }
        Vector3 normalized = vector.normalized;
        Transform transform = AddHold(e.v1, up, fn, activeGameObject.transform).transform;
        for (float num = 0.2f; num < vector.magnitude; num += 0.2f)
        {
            transform = AddHold(e.v1 + normalized * num, up, fn, transform).transform;
        }
    }

    private GameObject AddHold(Vector3 position, Vector3 up, Vector3 fn, Transform prev)
    {
        GameObject gameObject = new GameObject();
        gameObject.transform.position = position;
        gameObject.tag = "Anchor";
        gameObject.name = "ClimbHold";
        gameObject.layer = 19;
        gameObject.isStatic = true;
        gameObject.transform.rotation = Quaternion.LookRotation(-fn, up);
        gameObject.transform.parent = activeGameObject.transform;
        return gameObject;
    }

    private bool TrianglesEqual(Triangle t1, Triangle t2)
    {
        if (t1.v1 == t2.v1 && t1.v2 == t2.v2)
        {
            return t1.v3 == t2.v3;
        }
        return false;
    }

    private bool TrianglePairsContains(Triangle t1, Triangle t2)
    {
        for (int i = 0; i < trianglePairs.Count; i++)
        {
            TrianglePair trianglePair = trianglePairs[i];
            if ((TrianglesEqual(t1, trianglePair.t1) || TrianglesEqual(t1, trianglePair.t2)) && (TrianglesEqual(t2, trianglePair.t1) || TrianglesEqual(t2, trianglePair.t2)))
            {
                return true;
            }
        }
        return false;
    }

    private bool FindSharedEdge(Vector3 v1, Vector3 v2, Vector3 v3, Vector3 vt1, Vector3 vt2, Vector3 vt3, out SharedEdge e)
    {
        Vector3[] array = new Vector3[3]
        {
                v1,
                v2,
                v3
        };
        Vector3[] array2 = new Vector3[3]
        {
                vt1,
                vt2,
                vt3
        };
        for (int i = 0; i < array.Length; i++)
        {
            for (int j = 0; j < array2.Length; j++)
            {
                if (!(array[i] == array2[j]))
                {
                    continue;
                }
                for (int k = 0; k < array.Length; k++)
                {
                    for (int l = 0; l < array2.Length; l++)
                    {
                        if (k != i && l != j && array[k] == array2[l])
                        {
                            e = default(SharedEdge);
                            e.v1 = array[i];
                            e.v2 = array[k];
                            return true;
                        }
                    }
                }
            }
        }
        e = default(SharedEdge);
        return false;
    }

    private Vector3 GetNormal(Triangle t)
    {
        Vector3 lhs = t.v2 - t.v1;
        Vector3 rhs = t.v3 - t.v2;
        return Vector3.Cross(lhs, rhs).normalized;
    }
}

```

This is really cool. However, it ends up creating an unreasonable amount of `ClimbHold` gameobjects in your scene. For instance, a simple 10x10x10 cube will end up as a parent of over 200 `ClimbHold` gameobjects!

I had an idea to only generate `ClimbHolds` within a certain Player radius and delete them again when outside of the radius, but this too would create too much overhead. So the question is, what is a good way to find climb hold annotations of meshes in a scene, in a way that still allows for good performance?

# Answer
> I had an idea to only generate ClimbHolds within a certain Player radius and delete them again when outside of the radius, but this too would create too much overhead. So the question is, what is a good way to find climb hold annotations of meshes in a scene, in a way that still allows for good performance?

The answer is in array reuse and a fast radius calculation.

The radius calculations for each direction on the grid needs to use the Manhattan distance `abs(dx) + abs(dy) + abs(dy)`.

The size of the computed grid array is 1.5 times the max movement speed, rounded up to the next int, in each direction (should be square, or a box circumscribed about the radius, but much faster and known at design time), to allow per-computation time and loading allowance for multiple meshes.

The array would contain an array of `ClimbHold` instances to be checked against. Obejcts falling into multiple grids are stored multiple times.

When the position moves outside the current grid square, shift the entire array and fill in the missing cells.

The "trick" here is after the initial load computations on the array, only new new elements require computation.

The real risk is in memory fragmentation, but given the released memory is close in size to the new allocated size(if not a different pool will be used, giving the same end effect), fragmentation will be handled by the GC in a uniform manner when needed.
> 0 votes

---
Tags: unity, mesh, computational-geometry
---


title: Physics update frequency feasibility

text:
# Question
Title: Physics update frequency feasibility
I want to create an offline 2D platformer that is not very physics heavy. After a lot of consideration, I've decided to run most of the physics at a fixed rate of 480hz, and I'm not experiencing any issues with it at the moment.

However, I'm using Gamemaker Studio and although I'm trying to write code as efficiently as possible, I'm worried that I will run into problems further into development when considering lower-end devices such as consoles. I have absolutely no idea if this is too demanding of a task for this kind of game development software and I don't want to run into any issues, especially when considering console ports in the future.

Since I have pretty much no experience on this topic, is it worth writing an engine from scratch in a lower-level language, or will I be okay provided that I keep the scope of the game small enough? The game runs fine on older laptops, but I don't have any convenient way to test consoles yet, and I'm still quite early into development so I'm not sure that would help.

This is probably a dumb question, but I'm more of a designer than a programmer and I really don't have any prior experience to know if this is a good idea or not. Typically games written in this software run at 60 updates a second albeit not very well optimized.

I'm curious to know if anyone has any experience they could share that will help me with the decision.

# Answer
You should run your physics as often as you need for the project, but 480 seems awfully high. What is your need for it? However heavy your physics calculations will be, you'll still use 8 times more resources than 60 ticks.

Don't get me wrong, higher tick rates are used... but typically for things like car sims, etc. I can see some value of going higher than 60 maybe for something like angry birds, but generally speaking, I'd try to avoid it. From the other perspective, many FPS games have tickrate on servers even lower than 60.
> 0 votes

---
Tags: game-maker, fixed-timestep, game-maker-studio-2
---


# Question
Title: Efficient way to organize your collectible Actors
Assuming I want to make a RPG, where I can pick up different stuff, like plants and weapons.

How would you create the Actors?

More precisely:

Would you create an Actor for every item, maybe deriving from a super class called "collectible"? Or would you rather just use one Actor, "collectible", where you can set the Mesh and Meta-Infos (for Inventories for example) in the Instances placed in the Editor? Or maybe even a class "collectible" which reads information from a different text-file-format, where you also choose the file directly for every Instance?

Does it matter? Is it just personal style preference?

What (in general, of course it varies depending on the implementation) is more efficient?

# Answer
> 0 votes
The answer depends on the flexibility versus speed required.

A fixed single object is faster but larger in terms of memory and rigidness.

The larger memory footprint is as compared to a small number of loaded sub-classes, which depends on the use case.

Sub-classing allows more flexibility through dynamic resolution, but is slower.

There is no best answer for every scenario.

Usually personal preference takes over, but careful analysis provides better results in the long term.

# Answer
> 0 votes
What is collectible from data perspective (30 rounds of .45 ACP) should be separated from what is the collectible object that's actually in the world (actor with glowing and rotating magazine mesh, collision box, etc) and the communication to the player should be handled by some sort of message.

Therefore, I could add something to the player inventory by a simple message from anywhere - could be a proximity thing, could be story trigger, could be a simple collectible ...

And for the collectible, I'd have an Actor with the possibility to modify it's mesh, name, etc. for simple stuff (say floating blobbing coin, or ammo, or...). For some hero item, or whatever I'd be free to have a custom special actor since the only limiting part would be sending the message.

---
Tags: c++, unreal, blueprints
---