# Quickest way to sort an list with a LARGE amount of elements

I hate asking so many questions but hey, i got a grid system and i wanna connect it all together atm am using

``````        for (int i = 0; i < Nodes.Count; i++)
{
for (int o = 0; o < Nodes.Count; o++)
{
if (Vector3.Distance(Nodes[i].Position, Nodes[o].Position) < 1.9)
{
if (Physics.Linecast(Nodes[i].Position, Nodes[o].Position) == false)
{
}
}
}
}
``````

the Nodes count list can get very large just wondered if theres a better way someone can think of?

is this a grid, or a collection of loose points?

grid

Can you guarantee that the Nodes are in the list in a particular order? E.g. first grid row first from left to right, then the second grid row from left to right, etc?

that i can, and its in the order that you said - taking into account theres also multiple levels but lets worry about that atm

~Popper

• and at this rate am gonna have to put you too in the credits if i use this script in a commecial game >…<

OK, so you know the number of nodes in one row - call it the ‘width’ of the grid - so you can convert between (x,y) grid coordinates and indices:

index(x, y) = y * width + x

So for each node N, you can loop through only the 8 neighbouring ones, instead of the entire list. (Assuming that each node is 1 unit in size, nodes in a radius of 1.9 will only be the neighbouring 8).

Then, because you’re linecasting, you know that if A can see B, B must be able to see A. So you don’t need to check 8 neighbours per node, you need only check 4; you let the other 4 ‘check you’ when it comes to their turn later.

kinda think i know what you mean, ill give it a shot and get back to you

lmao nope looking at your post and cant figure it out…

sorry feeling like a right noob atm…

FYI, linecasts are expensive, so if you’re doing this in Update() then I would suggest looking for a completely different solution to your problem.

Where did you pull that from?

As far as I understand it LineCast/Raycast are actually the most efficient way to do LOS between points

linecast isnt in a update nor would i ever put linecast/raycast or any kind of cast in a update or any update per fram function.

the linecast is basicly there to stop it from connecting to a node through the ground like ramps or stairs for instance.

Until Diablo can justify his claim, I wouldnt worry too much about it… I would like to know what the ‘better’ solution is since linecast is so bad though.

the Unity documentation shows its usage within update…

have to say i also dont agree with his statement, ive done my research and tests on using both linecast and raycast and found them both the be quick and effective.

dont have document memory usage though so that might be what his on about.

~Popper

Im pretty sure I recall a full LOS algoritm that was doing up to 50,000 raycasts per frame and still getting good fps, so yeah who knows. Genuinely interested though.

as am i.

any chance you could give me a psuedo code???

For a node at index N, its neighbors are:

``````(N - 1 - width) (N - width) (N + 1 - width)
(N - 1)                           (N + 1)
(N - 1 + width) (N + width) (N + 1 + width)
``````

You need to do things a little differently at the edges, but I imagine you can figure that out. This reduces your number of linecasts per node to a maximum of 8.

The other optimization is to only check half the nodes, but if you’ve having trouble wrapping your head around the first part, implement it and get it working before worrying about the second part.

Are you looking for something like this?

Overall idea - ( Use Arrow keys to move it around )
http://dl.dropbox.com/u/32175794/Zombie_Gen_Start/WebPlayer.html

What you could do with it:
http://dl.dropbox.com/u/32175794/Demo/Demo.html