1
\$\begingroup\$

As the title says, I'm toying around with developing a 2D space RTS game. All of my units are spaceships that basically just shoot at one another, but they have to do a variety of other things as well: they have to "discover" (notify, draw, etc) other ships and planets not owned by the owner of this ship and within the arbitrary range of the ship's "scanners" (since they would otherwise be hidden), and if the ship is told to fire on an enemy ship, it needs to find the closest enemy (and fly to it if out of shooting range), and then shoot it obviously.

I've been wondering what efficient data containers could I use for the ships if there is going to be a large number of ships (100s to maybe 1000s) and why them? Also to note, is that ships must be distinguished by their owner (I may go to war with one player, so I obviously do not want my ships to search for ships of other players), where ownership will probably be represented by some integer (1 = player 1, 2 = player 2, etc) or maybe the unique pointer/memory address of a "player" object (0x4ff = player 1, 0x5ea = player 2, etc) or some other simple identifier.

I initially thought about using an array of vectors (C++), with the index of the array representing the player and each vector being the ships belonging to that player; then take all ships belonging to whatever player you are at war with and place them into a priority queue, whose root would be the enemy ship closest to a specific (friendly) ship and decide if its in range or not, but this seemed far too slow and memory-expensive, and didn't really address how to scan for ships/planets.

I then read up a few related posts about quadtrees and this lead me to other such tree data structures, like R-trees, that are also used for optimal spatial queries, but I do not quite understand exactly how they work and whether or not they would be best for me, so here we are.

\$\endgroup\$
2
  • \$\begingroup\$ The linked question may or may not satisfy your particular requirements, but questions asking for "the best" or "the most optimal" solution to broad topics such as storing unit data are generally too broad to be applicable here (as opposed to a forum like GDNet. You could consider asking there, or editing your question to specify the constraints of your problem more narrowly. \$\endgroup\$
    – user1430
    Commented Jul 2, 2015 at 1:48
  • \$\begingroup\$ Thanks for the suggestion, I'll give them a try too. I modified the question so as to ask for any efficient container, the linked question was somewhat helpful, since I do need collision detection, but it doesn't really address the unit detection as well. \$\endgroup\$
    – rawa
    Commented Jul 2, 2015 at 1:53

1 Answer 1

Reset to default
1
\$\begingroup\$

Use an influence map for target searching. Have a grid and on each node, reserve a spot in a collection of units for each team.

For each unit, generate a collection of coordinates within range and offset these coordinates as the unit moves. When a unit searches for a new target, enumerate over its coordinates within range. If another unit is on one of these coordinates, then that unit is within range.

Check this video out for visualization: https://www.youtube.com/watch?v=MEd6XV2Pecw.

I used this method for attack behaviors between about 1000 objects on 4 teams shown here: https://www.youtube.com/watch?v=y_ewoxlZlgc.

This target searching should be used as a broadphase. Once a target is acquired, range checks should still be done for more accuracy but the overhead for that is so small it's insignificant.

\$\endgroup\$
5
  • \$\begingroup\$ Great videos, thanks! One quick follow up question: by grid and node do you mean a node in a quadtree? \$\endgroup\$
    – rawa
    Commented Jul 2, 2015 at 4:25
  • \$\begingroup\$ Quad trees are a way to partition (divide into smaller groups), explained here: http.cs.berkeley.edu/~demmel/cs267/lecture26/lecture26.html. They can be used for grids, spaces, and indexes. With the influence map, you're already only checking the relevant nodes so there's no need to use a quad tree. \$\endgroup\$
    – JPtheK9
    Commented Jul 2, 2015 at 5:51
  • \$\begingroup\$ So how would you suggest dividing up a grid then? My map size is quite large (5000 to 7000 pixels squared), so using each coordinate as a node seems far too expensive. I figured using nodes of squares of 10x10 pixels or 50x50 pixels or something, but I was wondering how you would suggest handling the cases when a unit is overlapping multiple nodes? \$\endgroup\$
    – rawa
    Commented Jul 2, 2015 at 17:45
  • \$\begingroup\$ You can make your nodes however large or small as you need. Remember that this method of target searching is a broadphase so accuracy is not a big deal. A unit should never be overlapping multiple nodes because the node the unit is on is determined by rounding its position (its collider is not taken into account; if it is, then you need to generate a collection of coordinates the unit stands on and offset that when it moves but that's much more performance-intensive and unnecessary for a broadphase). \$\endgroup\$
    – JPtheK9
    Commented Jul 2, 2015 at 20:45
  • \$\begingroup\$ Check out the visualization video I put up. The coordinates of a unit are only offset after the unit moves a certain distance. It's not smooth at all because the position of the unit is rounded to an integer to fit a coordinate on the grid. \$\endgroup\$
    – JPtheK9
    Commented Jul 2, 2015 at 20:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .