This is what I’ve been cooking for the last days. It’s a basic path-finding AI that is not using A*.
The idea is that if all obstacles have ‘waypoints’ in corners, then walking from one waypoint to another you should be able to go around all obstacles. The waypoints are connected forming a graph. There are a lot of graph walking algorithms but I’m not using any of them to navigate (Dijkstra’s algorithm is only used when generating the map). All the AI needs to know is how far it is from one waypoint to all other waypoints. To determine what waypoints to check pre-generated visibility polygons are used.
At this point it sometimes gets stuck from time to time and the path chosen is sometimes weird, but in most cases it works.
Here’s a little demo and level editor:
sendspace.com/file/vtysot