• Create Account

### #Actualdmatter

Posted 12 June 2012 - 03:47 PM

I'm very sorry, but I'm still not getting it :/

No worries, you'll kick yourself though because it's quite elegantly simple.

Let's say I have 100 enemies and 100 friendlies.
You're telling me that I can find the best possible path from every enemy to every friendly (and viceversa) with only two breadth-first searches?

Not quite, but the best possible path from every enemy to every friendly isn't what you need. What you need is the best path for each enemy to its nearest friendly (and viceversa) and that can be done with just two search one for each type to generate your walkmaps.

Each cell in the walkmap represents the distance from that cell to an entity, so a unit sitting on that cell should examine the surrounding cells and pick one that is lower (and/or perhaps equal) to the value of the cell it is sat on.

Where do I have to start the searches at?

As you know a breadth-first search is based on a queue, you enqueue stuff to the back and dequeue stuff from the front.

To start the search you seed your queue with the cells of all entities (let's say all enemies) and mark them with a distance of 0.
Pop a cell off the front of the queue, add its surrounding neighbour cells to the back of the queue and mark each neighbour with a distance of 1+ whatever the central cell is marked as (e.g. 0+1 = 1), if you come across any neighbour cells that are already marked with a value then leave them alone (don't enqueue and don't change their value).
Loop until the queue is exhausted.

### #3dmatter

Posted 12 June 2012 - 02:23 PM

I'm very sorry, but I'm still not getting it :/

No worries, you'll kick yourself though because it's quite elegantly simple.

Let's say I have 100 enemies and 100 friendlies.
You're telling me that I can find the best possible path from every enemy to every friendly (and viceversa) with only two breadth-first searches?

Not quite, but the best possible path from every enemy to every friendly isn't what you need. What you need is the best path for each enemy to its nearest friendly (and viceversa) and that can be done with just two search one for each type to generate your walkmaps.

Each cell in the walkmap represents the distance from that cell to an entity, so a unit sitting on that cell should examine the surrounding cells and pick one that is lower (and/or perhaps equal) to the value of the cell it is sat on.

Where do I have to start the searches at?

As you know a breadth-first search is based on a queue, you enqueue stuff to the back and dequeue stuff from the front.

To start the search you seed your queue with the cells of all entities (let's say all enemies) and mark them with a distance of 0.
Pop a cell off the front of the queue, add its surrounding neighbour nodes to the back of the queue and mark each neighbour with a distance of 1+ whatever the central node is marked as (e.g. 0+1 = 1), if you come across any neighbour nodes that are already marked with a value then leave them alone (don't enqueue and don't change their value).
Loop until the queue is exhausted.

### #2dmatter

Posted 12 June 2012 - 02:21 PM

I'm very sorry, but I'm still not getting it :/

No worries, you'll kick yourself though because it's quite elegantly simple.

Let's say I have 100 enemies and 100 friendlies.
You're telling me that I can find the best possible path from every enemy to every friendly (and viceversa) with only two breadth-first searches?

Note quite, but the best possible path from every enemy to every friendly isn't what you need. What you need is the best path for each enemy to its nearest friendly (and viceversa) and that can be done with just two search one for each type to generate your walkmaps.

Each cell in the walkmap represents the distance from that cell to an entity, so a unit sitting on that cell should examine the surrounding cells and pick one that is lower (and/or perhaps equal) to the value of the cell it is sat on.

Where do I have to start the searches at?

As you know a breadth-first search is based on a queue, you enqueue stuff to the back and deqeue stuff from the front.

To start the search you seed your queue with the cells of all entities (let's say all enemies) and mark them with a distance of 0.
Pop a cell off the front of the queue, add its surrounding neighbour nodes to the back of the queue and mark each neighbour with a distance of 1+ whatever the central node is marked as (e.g. 0+1 = 1), if you come across any neighbour nodes that are already marked with a value then leave them alone (don't enqueue and don't change their value).
Loop until the queue is exhausted.

### #1dmatter

Posted 12 June 2012 - 02:16 PM

I'm very sorry, but I'm still not getting it :/

No worries, you'll kick yourself though because it's quite elegantly simple.

Let's say I have 100 enemies and 100 friendlies.
You're telling me that I can find the best possible path from every enemy to every friendly (and viceversa) with only two breadth-first searches?

That's right. Two search one for each type to generate your walkmap. Each cell in the walkmap represents the distance from that cell to an entity, so a unit sitting on that cell should examine the surrounding cells and pick one that is lower (and/or perhaps equal) to the value of the cell it is sat on.

Where do I have to start the searches at?

As you know a breadth-first search is based on a queue, you enqueue stuff to the back and deqeue stuff from the front.

To start the search you seed your queue with the cells of all entities (let's say all enemies) and mark them with a distance of 0.
Pop a cell off the front of the queue, add its surrounding neighbour nodes to the back of the queue and mark each neighbour with a distance of 1+ whatever the central node is marked as (e.g. 0+1 = 1), if you come across any neighbour nodes that are already marked with a value then leave them alone (don't enqueue and don't change their value).
Loop until the queue is exhausted.

PARTNERS