CODEWITHSUNDEEP
c++algorithmpoints
noisy cat
noisy cat

Reputation: 3065

C++ finding n points as close as possible to given xy

In RTS games, when you move some units, they find path and go to the places that are the closest to the selected place. I dont know how to select those places, I mean the target points for each unit.

For example, when I send 9 troops, I want them to have TARGETS like this:

. - empty, 
T - targets for units, 
O - the place that I've choosen to move them, target for unit too
.....
.TTT.
.TOT.
.TTT.
.....

Pathfinding algorithm is ready, just I need to generate the list (or vector) of target points, one for each unit. I dont want the complete code, but just some advices and ideas... Well I have to mind that not all places are walkable...

Thanx for any replies and sorry for my bad english...

Upvotes: 0

Views: 225

Answers (2)

amit
amit

Reputation: 178521

You could use a BFS from the allocated point. "Fill" the selected tile with a unit if it is a tile that can hold a unit [not an obstacle]. Keep doing it until you "exhausted" the number of units.

In pseudo-code:

selectTargetLocation(point,units):
  currUnit <- 0
  queue<- new queue
  visited <- {}
  map<unit,point> <- empty map
  queue.push(point)
  while (queue.empty() == false): 
     current <- queue.takeFirst()
     visited.add(current)
     for each p such that p and current are neighbors: //insert neighbors to queue
          if p is not in visited: 
                queue.push(p)
     if current is not an obstacle: 
         map.put(unit[currUnit++],current) 
     if (currUnit == units.length) break //break when exhausted all units
  return map

Upvotes: 1

Tibi
Tibi

Reputation: 3875

My idea would be like this: first, test if the destination is occupied, or a unit already has that destination. If this is the case, than you need to find a close point that is free. You could push all the near points to a queue, of the current point and so on... similar to fill algorithm), until you find a point that is not occupied. Then, find a path to that location.

Upvotes: 1

Related Questions