Tile vs Polygon Collisions

Game Mechanics
#1

Howdy!

Right now I’m knee-deep into the underlying data structures for my project, namely the map/collision system. Originally I expected to make the game run on a tile-based map, so I could rip off be inspired by Notch’s Minicraft (Ludum Dare entry).

But as I’ve got to implementing the system, and seeing how I intend to have a line-of-sight lighting system, I’ve been thinking it might be more optimal to have an underlying polygonal collision structure to handle both collisions and lighting, which, funny enough, would be very similar to how the original DooM games did it (For those who don’t know, my project is a top-down version of DooM).

So my question would be, what is the better approach? These are some of the requirements.

  • Visual representation is still a tilemap, so polygons must adhere to “manhattan” geometry, that is, 90º or 45º angles between lines, and all line lengths are integers (multiples of the predefined cell size).
  • Must run smoothly with a large number of entities.
  • Different areas (sectors) can have a different ambient light levels.
  • Small network footprint as cooperative LAN gameplay is a major objective.
  • Maps need be procedurally generated.

I’m leaning towards polygons for several reasons. Chief among them is that it’s easier to represent a polygon mathematically. Additionally, by dividing the game area in “sectors”, I can sort different areas into drawing/collision lists (something like BSP or portals) for more efficiency. I even might have the fringe benefit of allowing sectors to exist over one another, or even non-euclidean map structures, simply by joining “sector” edges independently of their map coordinates.

But, as is to be expected, I’m mister noobness here, so would like the board’s opinion.

Oh, few caveats:

  • Java2d Rendering: yes, I know, not optimal, etc. As I’ve said before, I want to implement it all by hand before I rely on pre-packaged solutions.
  • I want to implement it all: I’m already looking at Straightedge for inspiration / ideas, but I really want to manually implement everything myself to better learn the nuts and bolts of the system, so I’m not interested in API recommendations, but rather on a discussion about the theoretical advantages / disadvantages of each system. :slight_smile:

So, discuss! (And thanks in advance)

#2

Thought I’d add some more info on what I’m planning and doing. Here’s a quote from my devlog:

The animation shows, in no particular order:

  • Sector Lines: Inspired by how the original DooM handled it’s map system, the sector edges handle collisions, area transitions, and a few other things.

Up in the animation you can see the following:
[list]
[li]Yellow: Solid edges.

  • Green: Non-Solid edges.
  • Cyan: Edge normals, that is, where the “wall” is facing.
  • Blue: Edge’s starting point, as they are actually vectors, with the normal pointing to the right.

No, I didn’t forget about the red lines…

[/li]

  • Collision Groups: One of the reasons why I chose this arrangement is to simplify collision calculations. The idea is that sector edges are organized in groups based on their normals (in other words, based on where the “walls” are facing). When an object moves, it only checks if collisions happen with edges in a group that would collide with it’s movement vector. In other words, if an object moves to the left, collision will only be checked with edges facing to the right.

In the animation this is represented by the Red edges. When the Doomie moves into a given direction, the edges being checked for collision (that is, those part of the appropriate collision group) are being painted red.

Note that the diagonal edges light up more often, as they are part of two collision groups at once.

[/list]

Next steps are as follows:

  • Merge the Sector and Tilemap code, so tilemaps are generated based on the sector’s collision layout (Right now I have manually made them match, but they are unrelated pieces).

  • Improve the collision group sorting. The idea is to have the collision groups sorted front to back, or, in other words, organized based on position to avoid detecting a collision with an edge that is behind another edge.

#3

Thought I’d add some more info on what I’m planning and doing. Here’s a quote from my devlog:

The animation shows, in no particular order:

  • Sector Lines: Inspired by how the original DooM handled it’s map system, the sector edges handle collisions, area transitions, and a few other things.

Up in the animation you can see the following:
[list]
[li]Yellow: Solid edges.

  • Green: Non-Solid edges.
  • Cyan: Edge normals, that is, where the “wall” is facing.
  • Blue: Edge’s starting point, as they are actually vectors, with the normal pointing to the right.

No, I didn’t forget about the red lines…

[/li]

  • Collision Groups: One of the reasons why I chose this arrangement is to simplify collision calculations. The idea is that sector edges are organized in groups based on their normals (in other words, based on where the “walls” are facing). When an object moves, it only checks if collisions happen with edges in a group that would collide with it’s movement vector. In other words, if an object moves to the left, collision will only be checked with edges facing to the right.

In the animation this is represented by the Red edges. When the Doomie moves into a given direction, the edges being checked for collision (that is, those part of the appropriate collision group) are being painted red.

Note that the diagonal edges light up more often, as they are part of two collision groups at once.

[/list]

Next steps are as follows:

  • Merge the Sector and Tilemap code, so tilemaps are generated based on the sector’s collision layout (Right now I have manually made them match, but they are unrelated pieces).

  • Improve the collision group sorting. The idea is to have the collision groups sorted front to back, or, in other words, organized based on position to avoid detecting a collision with an edge that is behind another edge.