# Simplify nodes in a grid

## Recommended Posts

thefollower    354

Hello

I have a basic node system that stores points as well as the points they are connected to in my JavaScript like this:

var path    = [];


Now the end result looks something along the lines of this in my game:

The yellow dots represent the nodes stored in my path data. Now the question is how do i simplify this for when a user is building a road on the map so it automatically corrects the data.

Essentially if a user builds an intersection the nodes will update accordingly to keep the data clean and simple here is an example with the nodes in the place they should be:

The logic to do this seems quite complex and am hoping for some guidance on the best way to do this, i don't really know where to begin with adding the functionality to do this. The paths can go in 8 compass directions, N,S,E,W,NE,SE,SW and NW.

Edited by thefollower

##### Share on other sites
Aardvajk    13207
Quick thought, probably wrong, but is it not just if a cell has more or less than two neighbours? That covers the cases you posted at least.

##### Share on other sites
lightxbulb    1164

It's not readily evident what you're trying to do from your explanation.

Now the question is how do i simplify this for when a user is building a road on the map so it automatically corrects the data.

What do you mean by "simplify", and "corrects the data", what do you perceive as incorrect?

Essentially if a user builds an intersection the nodes will update accordingly to keep the data clean and simple

What do you mean by "update accordingly" and what would be "clean and simple", please define the problem more thoroughly - what is it exactly that you want to achieve? How does the current situation differ from what you'd like to achieve.

Edited by lightxbulb

##### Share on other sites
thefollower    354

It's not readily evident what you're trying to do from your explanation.

Now the question is how do i simplify this for when a user is building a road on the map so it automatically corrects the data.

What do you mean by "simplify", and "corrects the data", what do you perceive as incorrect?

Essentially if a user builds an intersection the nodes will update accordingly to keep the data clean and simple

What do you mean by "update accordingly" and what would be "clean and simple", please define the problem more thoroughly - what is it exactly that you want to achieve? How does the current situation differ from what you'd like to achieve.

The yellow dots show how the data should be represented - as simple points with the minimal amount required for any combination of path. As you see if a user builds an intersection, 2 nodes are removed, one is added in the middle of the intersection, and 2 are added to the horizontal path. The code needs to delete and insert these automatically based on the layout of the path so then my path finding has less work to do.

##### Share on other sites
lightxbulb    1164

"as simple points with the minimal amount required for any combination of path." - in your case it's not the minimal amount, I could get the same image without the node in the middle, so you actually want intersection to generate nodes at the intersections? "As you see if a user builds an intersection" - define builds an intersection - does he build it manually, or do you mean that by defining 2 roads that intersect - the program should recognize this intersection? "2 nodes are removed, one is added in the middle of the intersection, and 2 are added to the horizontal path." - I lost you here, I think I get how you get the central node, but why do you remove nodes and why do you add 2 nodes to the horizontal path?

##### Share on other sites
thefollower    354

"as simple points with the minimal amount required for any combination of path." - in your case it's not the minimal amount, I could get the same image without the node in the middle, so you actually want intersection to generate nodes at the intersections? "As you see if a user builds an intersection" - define builds an intersection - does he build it manually, or do you mean that by defining 2 roads that intersect - the program should recognize this intersection? "2 nodes are removed, one is added in the middle of the intersection, and 2 are added to the horizontal path." - I lost you here, I think I get how you get the central node, but why do you remove nodes and why do you add 2 nodes to the horizontal path?

Without the node in the middle i don't see how a given sprite would know to change direction if it was for example a corner, you need to know the node location so once the sprite hits that point you can go in a different direction. Thats why the middle node exists.

Why would i not remove the original nodes they would be useless to the new intersection? And the end nodes represent the end of the path so nodes need to be there to know where the path ends.

##### Share on other sites
lightxbulb    1164

Can you show the image of where the original nodes were supposed to be, before what you are talking about happens?

Edited by lightxbulb

##### Share on other sites
thefollower    354

The first image shows the original nodes.

##### Share on other sites
lightxbulb    1164

And how exactly do you get the 2nd image without doing anything from the first image, it doesn't make sense at least to me. I think defining what "building an intersection" would help a lot, or you could just define the whole thing in terms of a graph so people won't have to guess what you are trying to do. Or just take some time to elaborate on exactly what you want to happen - the more concise information you give - the better an answer would people be able to give.

P.S. The terms you use are more than ambiguous, and while you may have an idea in your head of what you want to make - I can guess at least 10 scenarios from what you're saying.

Edited by lightxbulb

##### Share on other sites
thefollower    354

Its built like a city builder when building roads in simcity for example, by the user clicking and dragging a path through the original path to create a  + shaped path.

Edited by thefollower

##### Share on other sites
lightxbulb    1164

This is not helping...Can you explain in steps, without references to simcity if possible, what you want to get from this:

var path    = [];


Like type the structure you get, and explain by what rules you get it. As much as I like guessing games, I'd prefer knowing the rules to build the 2nd image from the first one. Just elaborate on the question and exactly what you want to get.

##### Share on other sites
thefollower    354

I just told you how they do it  you click on the map drag the road across horizontally and when you let go the road is built. Currently there is no game logic to update the nodes correctly so they wouldn't be "connected" like an intersection - you would get a path for the horizontal road like this:

var path    = [];

//horizontal path


Notice it is not connected to the vertical road yet because thats what i have difficulty understanding how to connected it all.

##### Share on other sites
lightxbulb    1164

By dragging the road - in which directions can I drag it(only vertically, only horizontally, alternating?)?

This code helps a lot - so you basically want to merge roads if they "touch" or intersect?

Edited by lightxbulb

##### Share on other sites
thefollower    354

Yes but also get rid of unnecessary nodes.

The paths can go in 8 compass directions up, down, left, right, and the 4 diagonal directions at 45 degree angles. Between any two nodes its always a straight line.

##### Share on other sites
lightxbulb    1164

You can run an algorithm on a grid - basically drop the nodes to begin with and when "draggin your road" just put a cell value of 1 for example and 0 for empty. Then you start at a cell with 1 and from there search horizontally till you reach an empty cell - then you register where it ends and you can save the coordinates and put a node there. You can do the same thing vertically and diagonally. Or you could create an instance of some structure Cell that would contain information on the 8 neighbouring cells then run an algorithm on all the cells. The other possibility is going with your variant, applying an algorithm to check for intersections and stuff, but the whole thing would get needlessly tricky.

Say I have a grid nxn, use an array to represent that grid, make every cell = 0 to begin with, whenever you draw a road put cell = 1. After this if you want you could create nodes by analyzing the grid - basically from a cell with value 1 you try to reach the end horizontally, when you reach the ends you put a node there, same for the other directions. Example(c++ code):

const unsigned int n = 10;
bool grid[n][n];
for(unsigned int i = 0; i<n;i++)
{
for(unsigned int j = 0; j<n; j++)
{
grid[i][j] = 0;
}
}

int findEndHorizontallyRight(int cellX, int cellY)
{
if(grid[cellX][cellY]==0)
return 0;
int x = cellX;
while(x<n-1)
{
if(grid[x+1][cellY]==0)
{
return x;
}
x++;
}
return x;
}

Edited by lightxbulb

## Create an account

Register a new account