Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Supergrid based pathfinding data structure #150

Open
PowerfulBacon opened this issue Feb 17, 2022 · 13 comments · May be fixed by #167
Open

Supergrid based pathfinding data structure #150

PowerfulBacon opened this issue Feb 17, 2022 · 13 comments · May be fixed by #167
Assignees
@PowerfulBacon
Labels
Engine Some internal engine changes Legendary

Comments

@PowerfulBacon
Copy link
Owner

PowerfulBacon commented Feb 17, 2022 •
edited
Loading

Store the world into chunks of a certain size.
These chunks will then be stored in a grid of nxn chunks, which will be stored in a grid of nxn chunks etc.
This allows us to determine if 2 points are accessible by moving up to the top level grid chunk and seeing if it is the same.
This would give us an either O(logn) or O(1) algorithm for determining if 2 points on an infinite grid are adjacent.

We need to think about only supergriding when necessary.

This is mainly for determining if 2 points are accessible to each other, the pathfinding itself will just use the A* pathfinding algorithm.
@PowerfulBacon
Copy link
Owner Author

image

@PowerfulBacon PowerfulBacon added the Engine Some internal engine changes label Feb 18, 2022
@PowerfulBacon PowerfulBacon self-assigned this Mar 14, 2022
@PowerfulBacon
Copy link
Owner Author

image

@PowerfulBacon
Copy link
Owner Author

image

@PowerfulBacon
Copy link
Owner Author

Turns out the solution to this problem actually becomes quite nice.

image

Break this down into a recursive grid

image

The top left case will be 0 all the time, since if we land somewhere in a parent cells top left, instead of calling the parent level we call the current level in which case we will fall in 1 of the other places. The only time we fall in 0 is if we are at (0, 0)

Landing in the top right or bottom left returns the value of n which is the ceiling of the log base n of the larger of the x / y coordinate position.

Landing in the bottom right means we have to shift the x and y into the top left corner and try again. This has a maximum recursion depth of log(n) and that only happens if we fall on a 1.

@PowerfulBacon
Copy link
Owner Author

image
image
image

@PowerfulBacon
Copy link
Owner Author

PowerfulBacon commented Mar 16, 2022 •
edited
Loading

image
Structure is successfully generated

``` Test Name: TestRegionWorldSection Test Outcome: Passed Result StandardOutput: [MESSAGE][16/03/2022 17:01:30] Generating region (0, 0) [MESSAGE][16/03/2022 17:01:30] Created new region 0 at (0, 0) [MESSAGE][16/03/2022 17:01:30] (0, 0) joined region 0 [MESSAGE][16/03/2022 17:01:30] (0, 0) joined region 0 [MESSAGE][16/03/2022 17:01:30] (1, 0) joined region 0 [MESSAGE][16/03/2022 17:01:30] (0, 1) joined region 0 [MESSAGE][16/03/2022 17:01:30] (2, 0) joined region 0 [MESSAGE][16/03/2022 17:01:30] (1, 1) joined region 0 [MESSAGE][16/03/2022 17:01:30] (0, 2) joined region 0 [MESSAGE][16/03/2022 17:01:30] (3, 0) joined region 0 [MESSAGE][16/03/2022 17:01:30] (2, 1) joined region 0 [MESSAGE][16/03/2022 17:01:30] (1, 2) joined region 0 [MESSAGE][16/03/2022 17:01:30] (0, 3) joined region 0 [MESSAGE][16/03/2022 17:01:30] (4, 0) joined region 0 [MESSAGE][16/03/2022 17:01:30] (3, 1) joined region 0 [MESSAGE][16/03/2022 17:01:30] (2, 2) joined region 0 [MESSAGE][16/03/2022 17:01:30] (1, 3) joined region 0 [MESSAGE][16/03/2022 17:01:30] (0, 4) joined region 0 [MESSAGE][16/03/2022 17:01:30] (5, 0) joined region 0 [MESSAGE][16/03/2022 17:01:30] (4, 1) joined region 0 [MESSAGE][16/03/2022 17:01:30] (3, 2) joined region 0 [MESSAGE][16/03/2022 17:01:30] (2, 3) joined region 0 [MESSAGE][16/03/2022 17:01:30] (1, 4) joined region 0 [MESSAGE][16/03/2022 17:01:30] (0, 5) joined region 0 [MESSAGE][16/03/2022 17:01:30] (6, 0) joined region 0 [MESSAGE][16/03/2022 17:01:30] (5, 1) joined region 0 [MESSAGE][16/03/2022 17:01:30] (4, 2) joined region 0 [MESSAGE][16/03/2022 17:01:30] (3, 3) joined region 0 [MESSAGE][16/03/2022 17:01:30] (2, 4) joined region 0 [MESSAGE][16/03/2022 17:01:30] (1, 5) joined region 0 [MESSAGE][16/03/2022 17:01:30] (0, 6) joined region 0 [MESSAGE][16/03/2022 17:01:30] (7, 0) joined region 0 [MESSAGE][16/03/2022 17:01:30] (6, 1) joined region 0 [MESSAGE][16/03/2022 17:01:30] (5, 2) joined region 0 [MESSAGE][16/03/2022 17:01:30] (4, 3) joined region 0 [MESSAGE][16/03/2022 17:01:30] (3, 4) joined region 0 [MESSAGE][16/03/2022 17:01:30] (2, 5) joined region 0 [MESSAGE][16/03/2022 17:01:30] (1, 6) joined region 0 [MESSAGE][16/03/2022 17:01:30] (0, 7) joined region 0 [MESSAGE][16/03/2022 17:01:30] (7, 1) joined region 0 [MESSAGE][16/03/2022 17:01:30] (6, 2) joined region 0 [MESSAGE][16/03/2022 17:01:30] (5, 3) joined region 0 [MESSAGE][16/03/2022 17:01:30] (4, 4) joined region 0 [MESSAGE][16/03/2022 17:01:30] (3, 5) joined region 0 [MESSAGE][16/03/2022 17:01:30] (2, 6) joined region 0 [MESSAGE][16/03/2022 17:01:30] (1, 7) joined region 0 [MESSAGE][16/03/2022 17:01:30] (7, 2) joined region 0 [MESSAGE][16/03/2022 17:01:30] (6, 3) joined region 0 [MESSAGE][16/03/2022 17:01:30] (5, 4) joined region 0 [MESSAGE][16/03/2022 17:01:30] (4, 5) joined region 0 [MESSAGE][16/03/2022 17:01:30] (3, 6) joined region 0 [MESSAGE][16/03/2022 17:01:30] (2, 7) joined region 0 [MESSAGE][16/03/2022 17:01:30] (7, 3) joined region 0 [MESSAGE][16/03/2022 17:01:30] (6, 4) joined region 0 [MESSAGE][16/03/2022 17:01:30] (5, 5) joined region 0 [MESSAGE][16/03/2022 17:01:30] (4, 6) joined region 0 [MESSAGE][16/03/2022 17:01:30] (3, 7) joined region 0 [MESSAGE][16/03/2022 17:01:30] (7, 4) joined region 0 [MESSAGE][16/03/2022 17:01:30] (6, 5) joined region 0 [MESSAGE][16/03/2022 17:01:30] (5, 6) joined region 0 [MESSAGE][16/03/2022 17:01:30] (4, 7) joined region 0 [MESSAGE][16/03/2022 17:01:30] (7, 5) joined region 0 [MESSAGE][16/03/2022 17:01:30] (6, 6) joined region 0 [MESSAGE][16/03/2022 17:01:30] (5, 7) joined region 0 [MESSAGE][16/03/2022 17:01:30] (7, 6) joined region 0 [MESSAGE][16/03/2022 17:01:30] (6, 7) joined region 0 [MESSAGE][16/03/2022 17:01:30] (7, 7) joined region 0 [MESSAGE][16/03/2022 17:01:30] Generating region (1, 0) [MESSAGE][16/03/2022 17:01:30] Created new region 1 at (1, 0) [MESSAGE][16/03/2022 17:01:30] (8, 0) joined region 1 [MESSAGE][16/03/2022 17:01:30] (8, 0) joined region 1 [MESSAGE][16/03/2022 17:01:30] (9, 0) joined region 1 [MESSAGE][16/03/2022 17:01:30] (8, 1) joined region 1 [MESSAGE][16/03/2022 17:01:30] (10, 0) joined region 1 [MESSAGE][16/03/2022 17:01:30] (9, 1) joined region 1 [MESSAGE][16/03/2022 17:01:30] (8, 2) joined region 1 [MESSAGE][16/03/2022 17:01:30] (11, 0) joined region 1 [MESSAGE][16/03/2022 17:01:30] (10, 1) joined region 1 [MESSAGE][16/03/2022 17:01:30] (9, 2) joined region 1 [MESSAGE][16/03/2022 17:01:30] (8, 3) joined region 1 [MESSAGE][16/03/2022 17:01:30] (12, 0) joined region 1 [MESSAGE][16/03/2022 17:01:30] (11, 1) joined region 1 [MESSAGE][16/03/2022 17:01:30] (10, 2) joined region 1 [MESSAGE][16/03/2022 17:01:30] (9, 3) joined region 1 [MESSAGE][16/03/2022 17:01:30] (8, 4) joined region 1 [MESSAGE][16/03/2022 17:01:30] (13, 0) joined region 1 [MESSAGE][16/03/2022 17:01:30] (12, 1) joined region 1 [MESSAGE][16/03/2022 17:01:30] (11, 2) joined region 1 [MESSAGE][16/03/2022 17:01:30] (10, 3) joined region 1 [MESSAGE][16/03/2022 17:01:30] (9, 4) joined region 1 [MESSAGE][16/03/2022 17:01:30] (8, 5) joined region 1 [MESSAGE][16/03/2022 17:01:30] (14, 0) joined region 1 [MESSAGE][16/03/2022 17:01:30] (13, 1) joined region 1 [MESSAGE][16/03/2022 17:01:30] (12, 2) joined region 1 [MESSAGE][16/03/2022 17:01:30] (11, 3) joined region 1 [MESSAGE][16/03/2022 17:01:30] (10, 4) joined region 1 [MESSAGE][16/03/2022 17:01:30] (9, 5) joined region 1 [MESSAGE][16/03/2022 17:01:30] (8, 6) joined region 1 [MESSAGE][16/03/2022 17:01:30] (15, 0) joined region 1 [MESSAGE][16/03/2022 17:01:30] (14, 1) joined region 1 [MESSAGE][16/03/2022 17:01:30] (13, 2) joined region 1 [MESSAGE][16/03/2022 17:01:30] (12, 3) joined region 1 [MESSAGE][16/03/2022 17:01:30] (11, 4) joined region 1 [MESSAGE][16/03/2022 17:01:30] (10, 5) joined region 1 [MESSAGE][16/03/2022 17:01:30] (9, 6) joined region 1 [MESSAGE][16/03/2022 17:01:30] (8, 7) joined region 1 [MESSAGE][16/03/2022 17:01:30] (15, 1) joined region 1 [MESSAGE][16/03/2022 17:01:30] (14, 2) joined region 1 [MESSAGE][16/03/2022 17:01:30] (13, 3) joined region 1 [MESSAGE][16/03/2022 17:01:30] (12, 4) joined region 1 [MESSAGE][16/03/2022 17:01:30] (11, 5) joined region 1 [MESSAGE][16/03/2022 17:01:30] (10, 6) joined region 1 [MESSAGE][16/03/2022 17:01:30] (9, 7) joined region 1 [MESSAGE][16/03/2022 17:01:30] (15, 2) joined region 1 [MESSAGE][16/03/2022 17:01:30] (14, 3) joined region 1 [MESSAGE][16/03/2022 17:01:30] (13, 4) joined region 1 [MESSAGE][16/03/2022 17:01:30] (12, 5) joined region 1 [MESSAGE][16/03/2022 17:01:30] (11, 6) joined region 1 [MESSAGE][16/03/2022 17:01:30] (10, 7) joined region 1 [MESSAGE][16/03/2022 17:01:30] (15, 3) joined region 1 [MESSAGE][16/03/2022 17:01:30] (14, 4) joined region 1 [MESSAGE][16/03/2022 17:01:30] (13, 5) joined region 1 [MESSAGE][16/03/2022 17:01:30] (12, 6) joined region 1 [MESSAGE][16/03/2022 17:01:30] (11, 7) joined region 1 [MESSAGE][16/03/2022 17:01:30] (15, 4) joined region 1 [MESSAGE][16/03/2022 17:01:30] (14, 5) joined region 1 [MESSAGE][16/03/2022 17:01:30] (13, 6) joined region 1 [MESSAGE][16/03/2022 17:01:30] (12, 7) joined region 1 [MESSAGE][16/03/2022 17:01:30] (15, 5) joined region 1 [MESSAGE][16/03/2022 17:01:30] (14, 6) joined region 1 [MESSAGE][16/03/2022 17:01:30] (13, 7) joined region 1 [MESSAGE][16/03/2022 17:01:30] (15, 6) joined region 1 [MESSAGE][16/03/2022 17:01:30] (14, 7) joined region 1 [MESSAGE][16/03/2022 17:01:30] (15, 7) joined region 1 [MESSAGE][16/03/2022 17:01:30] Joining region 1 to 0 [MESSAGE][16/03/2022 17:01:30] Shared parent level: 1 [MESSAGE][16/03/2022 17:01:30] Created new parent node 2 at depth 1 [MESSAGE][16/03/2022 17:01:30] Joined 1 --> 2 [MESSAGE][16/03/2022 17:01:30] Joined 0 --> 2 [MESSAGE][16/03/2022 17:01:30] Generating region (3, 0) [MESSAGE][16/03/2022 17:01:30] Created new region 3 at (3, 0) [MESSAGE][16/03/2022 17:01:30] (24, 0) joined region 3 [MESSAGE][16/03/2022 17:01:30] (24, 0) joined region 3 [MESSAGE][16/03/2022 17:01:30] (25, 0) joined region 3 [MESSAGE][16/03/2022 17:01:30] (24, 1) joined region 3 [MESSAGE][16/03/2022 17:01:30] (26, 0) joined region 3 [MESSAGE][16/03/2022 17:01:30] (25, 1) joined region 3 [MESSAGE][16/03/2022 17:01:30] (24, 2) joined region 3 [MESSAGE][16/03/2022 17:01:30] (27, 0) joined region 3 [MESSAGE][16/03/2022 17:01:30] (26, 1) joined region 3 [MESSAGE][16/03/2022 17:01:30] (25, 2) joined region 3 [MESSAGE][16/03/2022 17:01:30] (24, 3) joined region 3 [MESSAGE][16/03/2022 17:01:30] (28, 0) joined region 3 [MESSAGE][16/03/2022 17:01:30] (27, 1) joined region 3 [MESSAGE][16/03/2022 17:01:30] (26, 2) joined region 3 [MESSAGE][16/03/2022 17:01:30] (25, 3) joined region 3 [MESSAGE][16/03/2022 17:01:30] (24, 4) joined region 3 [MESSAGE][16/03/2022 17:01:30] (29, 0) joined region 3 [MESSAGE][16/03/2022 17:01:30] (28, 1) joined region 3 [MESSAGE][16/03/2022 17:01:30] (27, 2) joined region 3 [MESSAGE][16/03/2022 17:01:30] (26, 3) joined region 3 [MESSAGE][16/03/2022 17:01:30] (25, 4) joined region 3 [MESSAGE][16/03/2022 17:01:30] (24, 5) joined region 3 [MESSAGE][16/03/2022 17:01:30] (30, 0) joined region 3 [MESSAGE][16/03/2022 17:01:30] (29, 1) joined region 3 [MESSAGE][16/03/2022 17:01:30] (28, 2) joined region 3 [MESSAGE][16/03/2022 17:01:30] (27, 3) joined region 3 [MESSAGE][16/03/2022 17:01:30] (26, 4) joined region 3 [MESSAGE][16/03/2022 17:01:30] (25, 5) joined region 3 [MESSAGE][16/03/2022 17:01:30] (24, 6) joined region 3 [MESSAGE][16/03/2022 17:01:30] (31, 0) joined region 3 [MESSAGE][16/03/2022 17:01:30] (30, 1) joined region 3 [MESSAGE][16/03/2022 17:01:30] (29, 2) joined region 3 [MESSAGE][16/03/2022 17:01:30] (28, 3) joined region 3 [MESSAGE][16/03/2022 17:01:30] (27, 4) joined region 3 [MESSAGE][16/03/2022 17:01:30] (26, 5) joined region 3 [MESSAGE][16/03/2022 17:01:30] (25, 6) joined region 3 [MESSAGE][16/03/2022 17:01:30] (24, 7) joined region 3 [MESSAGE][16/03/2022 17:01:30] (31, 1) joined region 3 [MESSAGE][16/03/2022 17:01:30] (30, 2) joined region 3 [MESSAGE][16/03/2022 17:01:30] (29, 3) joined region 3 [MESSAGE][16/03/2022 17:01:30] (28, 4) joined region 3 [MESSAGE][16/03/2022 17:01:30] (27, 5) joined region 3 [MESSAGE][16/03/2022 17:01:30] (26, 6) joined region 3 [MESSAGE][16/03/2022 17:01:30] (25, 7) joined region 3 [MESSAGE][16/03/2022 17:01:30] (31, 2) joined region 3 [MESSAGE][16/03/2022 17:01:30] (30, 3) joined region 3 [MESSAGE][16/03/2022 17:01:30] (29, 4) joined region 3 [MESSAGE][16/03/2022 17:01:30] (28, 5) joined region 3 [MESSAGE][16/03/2022 17:01:30] (27, 6) joined region 3 [MESSAGE][16/03/2022 17:01:30] (26, 7) joined region 3 [MESSAGE][16/03/2022 17:01:30] (31, 3) joined region 3 [MESSAGE][16/03/2022 17:01:30] (30, 4) joined region 3 [MESSAGE][16/03/2022 17:01:30] (29, 5) joined region 3 [MESSAGE][16/03/2022 17:01:30] (28, 6) joined region 3 [MESSAGE][16/03/2022 17:01:30] (27, 7) joined region 3 [MESSAGE][16/03/2022 17:01:30] (31, 4) joined region 3 [MESSAGE][16/03/2022 17:01:30] (30, 5) joined region 3 [MESSAGE][16/03/2022 17:01:30] (29, 6) joined region 3 [MESSAGE][16/03/2022 17:01:30] (28, 7) joined region 3 [MESSAGE][16/03/2022 17:01:30] (31, 5) joined region 3 [MESSAGE][16/03/2022 17:01:30] (30, 6) joined region 3 [MESSAGE][16/03/2022 17:01:30] (29, 7) joined region 3 [MESSAGE][16/03/2022 17:01:30] (31, 6) joined region 3 [MESSAGE][16/03/2022 17:01:30] (30, 7) joined region 3 [MESSAGE][16/03/2022 17:01:30] (31, 7) joined region 3 [MESSAGE][16/03/2022 17:01:30] Generating region (2, 0) [MESSAGE][16/03/2022 17:01:30] Created new region 4 at (2, 0) [MESSAGE][16/03/2022 17:01:30] (16, 0) joined region 4 [MESSAGE][16/03/2022 17:01:30] (16, 0) joined region 4 [MESSAGE][16/03/2022 17:01:30] (17, 0) joined region 4 [MESSAGE][16/03/2022 17:01:30] (16, 1) joined region 4 [MESSAGE][16/03/2022 17:01:30] (18, 0) joined region 4 [MESSAGE][16/03/2022 17:01:30] (17, 1) joined region 4 [MESSAGE][16/03/2022 17:01:30] (16, 2) joined region 4 [MESSAGE][16/03/2022 17:01:30] (19, 0) joined region 4 [MESSAGE][16/03/2022 17:01:30] (18, 1) joined region 4 [MESSAGE][16/03/2022 17:01:30] (17, 2) joined region 4 [MESSAGE][16/03/2022 17:01:30] (16, 3) joined region 4 [MESSAGE][16/03/2022 17:01:30] (20, 0) joined region 4 [MESSAGE][16/03/2022 17:01:30] (19, 1) joined region 4 [MESSAGE][16/03/2022 17:01:30] (18, 2) joined region 4 [MESSAGE][16/03/2022 17:01:30] (17, 3) joined region 4 [MESSAGE][16/03/2022 17:01:30] (16, 4) joined region 4 [MESSAGE][16/03/2022 17:01:30] (21, 0) joined region 4 [MESSAGE][16/03/2022 17:01:30] (20, 1) joined region 4 [MESSAGE][16/03/2022 17:01:30] (19, 2) joined region 4 [MESSAGE][16/03/2022 17:01:30] (18, 3) joined region 4 [MESSAGE][16/03/2022 17:01:30] (17, 4) joined region 4 [MESSAGE][16/03/2022 17:01:30] (16, 5) joined region 4 [MESSAGE][16/03/2022 17:01:30] (22, 0) joined region 4 [MESSAGE][16/03/2022 17:01:30] (21, 1) joined region 4 [MESSAGE][16/03/2022 17:01:30] (20, 2) joined region 4 [MESSAGE][16/03/2022 17:01:30] (19, 3) joined region 4 [MESSAGE][16/03/2022 17:01:30] (18, 4) joined region 4 [MESSAGE][16/03/2022 17:01:30] (17, 5) joined region 4 [MESSAGE][16/03/2022 17:01:30] (16, 6) joined region 4 [MESSAGE][16/03/2022 17:01:30] (23, 0) joined region 4 [MESSAGE][16/03/2022 17:01:30] (22, 1) joined region 4 [MESSAGE][16/03/2022 17:01:30] (21, 2) joined region 4 [MESSAGE][16/03/2022 17:01:30] (20, 3) joined region 4 [MESSAGE][16/03/2022 17:01:30] (19, 4) joined region 4 [MESSAGE][16/03/2022 17:01:30] (18, 5) joined region 4 [MESSAGE][16/03/2022 17:01:30] (17, 6) joined region 4 [MESSAGE][16/03/2022 17:01:30] (16, 7) joined region 4 [MESSAGE][16/03/2022 17:01:30] (23, 1) joined region 4 [MESSAGE][16/03/2022 17:01:30] (22, 2) joined region 4 [MESSAGE][16/03/2022 17:01:30] (21, 3) joined region 4 [MESSAGE][16/03/2022 17:01:30] (20, 4) joined region 4 [MESSAGE][16/03/2022 17:01:30] (19, 5) joined region 4 [MESSAGE][16/03/2022 17:01:30] (18, 6) joined region 4 [MESSAGE][16/03/2022 17:01:30] (17, 7) joined region 4 [MESSAGE][16/03/2022 17:01:30] (23, 2) joined region 4 [MESSAGE][16/03/2022 17:01:30] (22, 3) joined region 4 [MESSAGE][16/03/2022 17:01:30] (21, 4) joined region 4 [MESSAGE][16/03/2022 17:01:30] (20, 5) joined region 4 [MESSAGE][16/03/2022 17:01:30] (19, 6) joined region 4 [MESSAGE][16/03/2022 17:01:30] (18, 7) joined region 4 [MESSAGE][16/03/2022 17:01:30] (23, 3) joined region 4 [MESSAGE][16/03/2022 17:01:30] (22, 4) joined region 4 [MESSAGE][16/03/2022 17:01:30] (21, 5) joined region 4 [MESSAGE][16/03/2022 17:01:30] (20, 6) joined region 4 [MESSAGE][16/03/2022 17:01:30] (19, 7) joined region 4 [MESSAGE][16/03/2022 17:01:30] (23, 4) joined region 4 [MESSAGE][16/03/2022 17:01:30] (22, 5) joined region 4 [MESSAGE][16/03/2022 17:01:30] (21, 6) joined region 4 [MESSAGE][16/03/2022 17:01:30] (20, 7) joined region 4 [MESSAGE][16/03/2022 17:01:30] (23, 5) joined region 4 [MESSAGE][16/03/2022 17:01:30] (22, 6) joined region 4 [MESSAGE][16/03/2022 17:01:30] (21, 7) joined region 4 [MESSAGE][16/03/2022 17:01:30] (23, 6) joined region 4 [MESSAGE][16/03/2022 17:01:30] (22, 7) joined region 4 [MESSAGE][16/03/2022 17:01:30] (23, 7) joined region 4 [MESSAGE][16/03/2022 17:01:30] Joining region 4 to 1 [MESSAGE][16/03/2022 17:01:30] Shared parent level: 2 [MESSAGE][16/03/2022 17:01:30] Created new parent node for 4, parent node 5 at depth 1 [MESSAGE][16/03/2022 17:01:30] Joined 4 --> 5 [MESSAGE][16/03/2022 17:01:30] Created new parent node 6 at depth 2 [MESSAGE][16/03/2022 17:01:30] Joined 5 --> 6 [MESSAGE][16/03/2022 17:01:30] Joined 2 --> 6 [MESSAGE][16/03/2022 17:01:30] Joining region 4 to 3 [MESSAGE][16/03/2022 17:01:30] Shared parent level: 1 [MESSAGE][16/03/2022 17:01:30] Joined 3 --> 5 ```

For 2D:
image

@PowerfulBacon
Copy link
Owner Author

TODO: Add in the ability to update a nodes solidity.

@PowerfulBacon
Copy link
Owner Author

When removing a region, we need to locate the shared parent then split it into 2 parts based on what should be connected.

@PowerfulBacon
Copy link
Owner Author

image

@PowerfulBacon
Copy link
Owner Author

image

@PowerfulBacon
Copy link
Owner Author

I think regions need to know what regions they are adjacent to in order to determine adjacentivity without iterating through every node in the network.

@PowerfulBacon
Copy link
Owner Author

image
image
image

@PowerfulBacon
Copy link
Owner Author

Currently the code to subdivide regions has issues
image
This is the output from that code

@PowerfulBacon PowerfulBacon linked a pull request Mar 19, 2022 that will close this issue
[TODO] Region pathfinding optimisations #167
Draft
@PowerfulBacon PowerfulBacon linked a pull request Mar 19, 2022 that will close this issue
Draft
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@PowerfulBacon PowerfulBacon

Labels
Engine Some internal engine changes Legendary
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

[TODO] Region pathfinding optimisations PowerfulBacon/GJ2022
1 participant
@PowerfulBacon