So, my game uses connected line segments for collision detection with the map. Maps are hand drawn and using bitmasks for collision makes it too difficult to get a nice "slide" effect (sliding along lines as you bump against them).. Now I need to implement some pathfinding given these constraints, and I'm looking for ideas. My first idea was to divide into tile-sized blocks and "draw" lines into them to find if they're passible. The problem with that is, there could be any number (well, maybe 3-4 max) lines crossing any given tile.

So I'm kind of stuck here. And just to make sure I don't get a bunch of answers on how to implement A*, I know how, it's just finding if a tile is passible and WHERE on that tile is passible that I'm having problems with. I could have a tile like this:

+--------+
|     |  |
|     |  |
|\    |  |
| \   |  |
+----|--+

It might be passible in between those lines if the characters collision box is small enough.

And maybe tiles is the completely wrong way to go, maybe even A* is the wrong way to go. Help would be appreciated...

[edit]
Sorry, the diagram somehow messes up. Imagine a tile with a line on either side with an open path up the middle.

Ya, but I don't think it's that simple. Imagine a tile with a L joint shape in it... I guess it's going to take a little more modification of the A* algorithm. I'll have to add X number of intermediate points per tile.

Thanks but I've avoiding a manual approach. Presently we have dozens of large maps, and there will be hundreds more. There's already a lot of processing that goes into each map. I need some way to generate nodes automatically.

The real pitfall is the fact that your map is hand-drawn as a whole. There are two possible solutions I can think of at the moment:

1) You manually create a pathnode graph for each map (kinda same way you have to do it for maps in UT for example). This will give you large control over the pathfinding - say you can have edges weighed by distance and also have additional information, e.g. how big objects can pass through.

There are several drawbacks: for large map with large open space areas you'll need to do lots of nodes in order to prevent bad looking movement. Also for nicer results more nodes should be created and thus more time will be spent.

2) As you mentioned above, you could overlay your map with square grid. The smoother the better, but not insanely smooth. Then put a path node into the middle of each square. During preprocessing of the map you'll build the graph via a simple algorithm: for each node you'll cast ray into all directions (4 or 8^[1]) and check whether the ray collides with the environment or not. If not then you can add the edge into the graph.

In both cases you can then use any graph algorithm for pathfinding. If you expect dynamic changes in the graph (like some paths being blocked by objects etc.) I'd advice to use the A*, if the graph will be static, you could use Floyd-Warshall to precompute paths and then poll them in constant time.

Obviously, if you look at the title of this thread, you should be able to tell that I know A* doesn't require tiles ... Anyhow, thanks for all of the info. I was googling around for navigation meshes, and it turns out there's a section in Game Programming Gems 1 about it, and I own that book, but haven't read most of it. So I'll give that a read. Thanks.

EDIT:

I tried 2 different algorithms (that I came up with myself...) to try and triangulate an area. Both of them had problems and I was growing tired of trying to fix them after 4 straight days of working on them. So I switched to a brute force method. The problem is, the results aren't pretty... My impression after reading about navigation meshes was that it doesn't matter what the triangles look like. But I wanted to ask to be sure... this is a screenshot of what a small area looks like after triangulating it with the brute force algorithm:

{"name":"ss.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/7\/37e33d62c8c2d88454dcd3a1b5933b6d.png","w":600,"h":622,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/7\/37e33d62c8c2d88454dcd3a1b5933b6d"}

Will that be ok for a navigation mesh?

The outer lines are the border.

I was thinking of connecting vertices that had an interior angle of 270 degrees or so, unless the line segments connecting them were shorter than some small value. The rest could be triangulated by adding more interior vertices (the rectangular areas on the left already have these) when a triangle has too small of an angle somewhere. Kind of thinking out loud here.

{"name":"602141","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/b\/e\/beb3238732b5f2a8e4972226ce42536a.png","w":600,"h":622,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/b\/e\/beb3238732b5f2a8e4972226ce42536a"}

Trent you may be slightly missing the point. You are not trying to solve the triangulation problem which is:

This is not what you are trying to do because this will only allow for navigation between vertices of your environment. As I've already mentioned, you should be adding vertices to navigate between. This is, in many ways, easier than the strict triangulation/tesselation problem.

Here's what I've got now:

{"name":"ss2.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/5\/d\/5d527061ac4e8635127d0cff7b6cabbe.png","w":600,"h":622,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/5\/d\/5d527061ac4e8635127d0cff7b6cabbe"}

The only problem seems to be some overlap in the bottom left corner. Not sure how I'm going to fix it, but it's late. I might come up with something tomorrow. This is the basic ear cutting method described in the document Gnolam linked (I had to improvise some because it seems to leave out important details).

EDIT:

I took the holes out of the left side until I get it right without holes.

EDIT:

I think I made some improvement... but now there are errors in the top right O_O... here's what it looks like:

{"name":"602144","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/7\/9\/79c907afd4da0d60bda6b75becd3792a.png","w":600,"h":622,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/7\/9\/79c907afd4da0d60bda6b75becd3792a"}

EDIT:

It's working, at least for this one set of test data:

{"name":"602145","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/7\/37fc455b1414967e48ca210a4bd9f2e0.png","w":600,"h":622,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/3\/7\/37fc455b1414967e48ca210a4bd9f2e0"}

Some areas look suspect but I scaled the points 3x and the thin triangles are distinct and correct. Thanks everyone.

EDITED: updated link

It doesn't, but I plan on adding support for holes in the next day or two (or however long it takes). I don't know how good it is. I'll find out once I try it on some more levels. The source code for what I've got now is here, anyway: http://trent.gamblin.ca/triangulate. There is room for improvement, notably the part where it checks every pixel on a line to see if it's outside the polygon, as I didn't know how to do that any better way.

Updated the post right after first adding it.

EDIT:

I'm not sure about this, but is it possible to pick separate polygons out of a stream with no markers? I'm guessing it's not. If that's the case then I'll either put markers in or have the user specify the start indices of each polygon (I'm talking about the outer polygon and the holes inside it). Which of those is preferable?

EDIT:

Back to this thread again, with some problems adding holes. I tried a bunch of different things, but mainly trying to stick with the ear clipping document. I create a 0 size "gap" leading to the nearest edge corner to the right. I inline the hole where it should appear in the main polygon, adding two extra vertices leading out of the hole, where it continues on as if the hole wasn't there. This is supposed to "just work" I guess, because it keeps the polygon simple. Well I'm just not getting anything to fill in triangles around the holes (or just a few). At best I had all of the triangles filled except 11, but I think this screenshot I'm going to post is my best effort so far, even though it has less fill ratio:

{"name":"602165","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/5\/d\/5d0d31325ee9c25288b409ab557a855d.png","w":600,"h":622,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/5\/d\/5d0d31325ee9c25288b409ab557a855d"}

The green lines are the outline of the polygon (you can see the "gaps" I put in, the first one is obvious and the other two are going to the same corner of the rectangular area. I don't know what I'm doing wrong, so I'm going to mull it over a bit without looking at the code... if anyone has experience with this and has some ideas on what might be wrong that would be great. I'll attach the source code. The "DL_List" stuff is just a simple doubly linked list I made up for this, if you want the code for that to test this I will upload it.

On a positive note, what you see is generated in 1 ms or a little above as opposed to 10 ms of my other attempt. I learned a few math tricks .

P.S.: I used a wide terminal to edit it, as it would have gotten down right ugly trying to fit it into 80 characters.

You'll see some markings "method 1" and "method 2" which are two slightly different approaches I'm playing with right now.

EDIT:

I think I finally got it. No telling until I start trying some pathfinding later on today. But it's all triangulated:

{"name":"triangulation-working.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/2\/423684268376000fe93bc2e6d1580325.png","w":600,"h":622,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/2\/423684268376000fe93bc2e6d1580325"}

If you're interested, the problem was twofold but both related. One of the "splits" I put it between a hole and the outside edge was going in where another split already went, so wires were crossed. Simple, just find the next exact same point further down (after the hole that was inserted.) The other one was related, it was also two lines crossing over each other but in the image there was no telling since it was a straight line for a triangle. A little investigation found these two errors out.

The final image took about 2.5 ms to generate triangles for. It can be optimized a lot, you could probably get near or under 1 ms without too much work. The source code is available here: http://trent.gamblin.ca/triangulate/

Yes, LoS check is the plan.

EDIT:

I found a bug after trying some new data. Also, new timing info: Was compiling with -g, no optimization. With optimization the same point set takes about 1.5 ms to triangulate.

I'll be updating the software as I find bugs or to optimize things. Probably not posting much in this thread unless someone responds. The web page will be kept up to date with bug fixes etc: http://trent.gamblin.ca/triangulate.

Funnily, I emailed the author of a triangulator about a commercial license around the time I started mine. I got an email response from him now that it costs $2500 for a license of the software :O. I guess I saved myself a bit of money and had fun/learned some things in the process. God, thank you for giving me a lot of free time so I can do these things on my own schedule

Haha. I'm not sure how to fix this one. It's beyond my capabilities.