I am making a 2d top-down programming game similar to robocode. There will be up to 1000 walls (lines) in the arena, and up to 50 robots. Each robot can see in a 90 degree arc, and cannot see through walls. I need an efficient way to calculate what each robot can see (other robots and walls). I already have a grid of bins implemented. I was wondering what is the most efficient way to tackle this problem.

It would be nice if the method also includes a way to draw the shadows for visualization, but this is not necessary.

I am using C++ and the Qt framework.

Summary: The main question is how to generate a list of robots and walls that each robot can see. For example:

Robot 1 can see:
    Robot 6
    Robot 15
    A wall from (50,60) to (70,80)

Robot 2 can see:

Well I'd suggest storing them in some kind of scene graph so that you only have to draw what you can see, and it would be easy to calculate what you can see. And for what they can see, i suggest raycasting or some simplified version of it

  • \$\begingroup\$ I had thought of this, but with raycasting, the rays spread out. At longer distances, the rays will miss some bins, and consequently, the walls and robots that are contained in those bins. \$\endgroup\$ – Joel Apr 18 '12 at 13:58
  • \$\begingroup\$ You raycast specifically to walls \$\endgroup\$ – CobaltHex Apr 18 '12 at 14:05
  • \$\begingroup\$ Wouldn't that be raytracing if the rays go from the walls to the robot? \$\endgroup\$ – Joel Apr 18 '12 at 14:08
  • \$\begingroup\$ Well you know what walls exist so you cast from the player to each wall within a range \$\endgroup\$ – CobaltHex Apr 18 '12 at 14:12
  • \$\begingroup\$ Ok. Here is what I'm thinking. I calculate an arc of 90 degrees with this algorithm: en.wikipedia.org/wiki/Circle_drawing_algorithm . The result will be a list of bins that are at a certain distance from the robot. Check for walls and robots in the bins. If there is a wall, don't continue to check behind it. For example, if my vision angle was 0 to 90, and a wall obstructed part of it, my new vision angle might be 0 to 50 and 60 to 90. Keep moving outwards and checking the bins in my vision angle until I do not have any vision angles left. \$\endgroup\$ – Joel Apr 18 '12 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.