Cutting to the chase here, I working on a game where ships are drawn not as bitmaps but as a simple collection of polygons, using al_draw_polygon and al_draw_filled_polygon.

My most complex ship calls al_draw_polygon and al_draw_filled_polygon together 62 times in total.

Now with my game, seeing a thousand ships on the screen (when zoomed out) is a common occurrence. But this slows the game to almost a halt, 62,000 calls to those functions being made every frame.

Even having 100 ships on screen (which is a pretty reasonable amount considering how small they are) slows down the game to a significant extent.

Any advice on how I can improve performance?

Yup, what Thomas said. When it comes to optimizing graphics in Allegro 5, it's all about reducing the number of calls to drawing functions. So use al_draw_prim(), (or even better yet, al_draw_vertex_buffer()), and pack as many vertexes as you can into each call.

If your data is structured correctly, a mediocre system should easily be able to handle the demands you describe and much much more.

A triangle is a polygon If your data is actually > 3 sides per polygon, you need to split the polygon into triangles that make up the polygon.

That shouldn't be a problem here. Pretty much all convex polygons can easily be seperated into multiple triangles by just connecting two of the vertices. When drawing your primitive, this shouldn't make any optical difference at all (unless you render a wireframe).

Very simple actually. Just connect any two vertices that are not yet connected to each other and repeat this until all vertices on each polygon are connected, in which case it's a triangle. As I mentioned, this only works for convex polygons, though.

IIRC al_draw_polygon() uses al_triangulate_polygon() and al_draw_prim() internally.

As for the original question, you may also need al_draw_indexed_prim(). Split up all polygons into a single array of triangles, then draw all the triangles just using a single function call.

Depends on how you're drawing the wireframe. Are you just using the wireframe mode of the graphics API? In that case, it will put a wireframe around all triangles. You could, however, write a shader to render the wireframe. In that case it would be up to you which edges would be rendered. Although this does require a certain shader version to make it look pretty (not much of a problem with OpenGL thanks to extensions, only with Direct 3D).

Hmm, any links or resources you could point me to that will show me how I could do that?

Hmm, what is the difference between al_draw_indexed_prim and al_draw_prim?

I have two links for your.

Solid Wireframe by NVIDIA
(Scroll down the list to Solid Wireframe)

This one looks great, but is a bit evolved to get to work, mainly because you need a geometry shader (which Allegro doesn't even support directly). However, it does already distinguish triangle edges from the edges of an n-sided polygon (four-sided in this case), so it should give you an idea of what you need. From what I remember, it does this by asuming a certain order of indices. That way it knows exactly which edges to skip.

Wireframe Shader Using Barycentric Coordinates

This one is a lot simpler and doesn't require a geometry shader, but probably doesn't look as good as the NVIDIA one. This is what I'm using for my game as well. The version here doesn't skip any edges, but it should be easy enough to add that by just doing what I already described above. This shader requires a certain function that is only available in certain shader models, though. For OpenGL this isn't much of a problem since you can just set the version to use in the shader itself. For HLSL it is a problem if you're using Allegro, because Allegro uses shader model 2.0 by default and has this value hardcoded somewhere in the source. You'd need at least pixel shader model 3.0 and for this you'd have to modify the source code of Allegro (this is exactly what I did). The shader itself is so simple that it's easy to tweak, though, and all it needs to work is an additional float3 for each vertex.

If you want to stick to shader model 2.0, you can still use the method above, but the edges of the wireframe will then have varying thickness depending on their distance from the camera. I'm not a fan of this, but maybe it's good enough for what you want to accomplish.

Also just doing a google search for "wireframe shader" should give you a lot more results to try out for yourself.