I am working on a 2D game using Allegro 4.9.x and am now onto the problem of a map format. I intend to use XML, as the game is made mostly in Lua (C++ simply to bridge Allegro and some other utility libraries with Lua), to store the map format. Now, the map format would be as follows:

• As a separate file or embedded in the map, an "object," which would be composed of the required variables (friction, damage, etc). These would also have a path to an image or animation, and a "bounding polygon" which may or may not be concave.

• In the actual map file, it would store a list of these "objects" and their positions, along with some other things, per layer. These "other things" could include the scroll speed and so on.

To cut it short, I want to have a polygon represent a platform/floor/non-interactive object. It would also be nice if I extend this to the actual game entities, which use skeletal animation (well, something similar, in order to give it a nice paper-doll effect and provide an easier, more flexible way of doing animations). I need this in order to handle collision detection and movement.

As an example, say this is an object:

I would like to turn the concave "bounding polygon" into something that would be easily manageable in Lua, for collision and similar. This could be turning the polygon into a bunch of triangles, etc. However, I don't want to have more than one polygon in the map format per object, unless turning a concave polygon into a bunch of triangles is far too hard/costly. I know how easy convex polygons are to do (take one point and create a triangle using two points, repeat), but I'd rather have the map format be nice and easy to read/write (either by a human or a computer).

Thanks for any help!

This may help...
http://www.alienryderflex.com/polygon/
and another thing that might
http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

If you want to turn a concave polygon into a bunch of triangles then you want to do polygon tesselation or triangulation. The good news is that GLU (the OpenGL Utility Library) includes a great tesselator and no actual OpenGL dependencies; it just shares the name and some of the API style. So my first tip would be just to link to and use that, irrespective of the means you are using for displaying graphics.

If you're otherwise looking for something that is easy to implement and not horribly inefficient (albeit it only does simple polygons — polygons for which the exterior lines never cross), look into ear clipping. You should probably look it up, but from memory it goes like this:

First categorise all points around the outside of the polygon as either convex (with an interior angle of less than or equal to 180 degrees) or reflex (an interior angle of greater than 180 degrees).

Then run through the list of convex points. Consider the triangles they make with the points immediately before them and after them on the polygon. If you can no other convex point is inside the triangle associated with a particular convex point then that complete triangle is an 'ear'. You can remove the triangle and add it to your triangulation. That also means removing the convex point from your list of points. Then inspect the two points it was connected to. If either is reflex, test whether it has become convex and, if so, add it to the convex list.

Repeat until the reflex list is empty, then triangulate the convex list as a simple convex polygon.

Ear clipping is O(n^2). The method used by GLU (monotone polygons - not too bad but definitely more complicated than ear clipping) is O(n log n). An O(n) algorithm is believed, or has possibly been proven, to exist but doesn't currently seem to be in the public domain of knowledge if it is known at all.

I looked closer at GLU (I had looked at earlier in my searches, but wasn't sure if I should use it) and see that this or the ear clipping method will work perfectly (there will be no intersections in the polygons).

Thank you!

You could look at http://tog.acm.org/editors/erich/ptinpoly/.

Above all, I wouldn't do the collision detection in Lua, but rather do it in C and expose the detection function to Lua. Lua is fast, but collision detection is one of the typical bottlenecks and worth the optimization.

The concave polygon can be separated into a few convex polygons; you only need to do it once per polygon, and you don't need to separate all the way down to triangles. All you need is a number of convex polygons; 5 are enough for your example. Once you have that, you can simply apply a separating axes algorithm to each polygon individually.
If it's for a side-scroller, you may want to handle horizontal and vertical collisions individually; in that case, you can divide the polygon into a bunch of strips and store the top and bottom coordinates for each; collision detection then works a lot like bounding-box.
Also, doing a first rough test to weed out the obvious non-collisions (e.g. a sphere-sphere test) is probably a good idea, and if you have lots of objects to test against each other, use some sort of space partitioning (axis sort being the easiest, followed by static sectors, and finally quadtrees) to reduce the number of checks.

Ideas for which could be construction of a leafy BSP or just sticking together triangles where possible after tesselation. I'm not sure if there are any better ways?

Per "room," there's probably going to be no more than 100 objects/entities. I will also be taking more consideration and not using a brute-force method to collision detection. Bounding box first, after a sector/quad-trees approach, as you said. I am not that silly!

I want this game to be more Lua-than-C++, so unless this really gets to be a major bottleneck, I will stick with Lua for the collision detection. I really enjoy making games in Lua, rather than having to drop into the manual memory allocation, static-typing, and so on of C++...

I feel with you on the subject, but most developers use scripting for game content (story events, AI, weapons etc). But hey, if you get it to work acceptably, good for you As long as you know that you are coding in a scripting language (and what restrictions that entail), and take that into consideration when designing things, you should be fine. I'm coding games in Ruby (possibly the slowest language on earth ), so I shouldn't even be giving my opinion on the matter