I'm creating a game with randomly generated dungeons. They consist of several rooms the size of the screen, but right now they are completely empty except for the enemies which makes for a rather boring game.

I want to put in objects that the player can't walk past, but obviously I can't place these completely random or I risk making the game impossible to finish. One way of solving it would be to create a straight path between the openings of a room and make it illegal to place objects on the path, but that'll probably look fake. Another way would be to do a pathfind after placing each objects, and if I can't find a path between all the openings I remove it again, but that feels a bit too much like brute force.
Is there some algorithm for finding A path between two points, not the shortest and straightest? Or do you have some other idea of how to solve this?

What you want to do is to make certain that the player is not blocked from accessing important areas within your room (treasure, exits, triggers, etc). So, after placing your objects, do a flood-fill from the entrance of the room and mark any unreachable areas as unreachable. Then you can either move important items in unreachable areas to reachable areas, or you can use some type of walk algorithm to tear down walls in between important-but-unreachable areas and the nearest reachable area. Playing around with your walk algorithm will give you good looking results.

Check the dev blog for Drillboid

One very simple way of ensuring that the game cannot be unsolvable would be to do similar to what you already proposed yourself:

Make a straight path between the openings of the room, but then again, do not make it straight. Give it 2-3 vertices somewhere along the path and offset those slighly (randomly). You end up with a more or less zigzag sequence of line segments.

Now, place your random stuff, except when an object's radius is [s]greater[/s] smaller than the distance to any line segment. Done.

By tweaking the number of intermediate vertices and the amount of random, you can change the look. You can also have two or three paths going from each opening to the other, the random variations giving a broader overall corridor (or several alternative corridors, depending on parameters).

http://roguebasin.ro...tegory:Articles

Several of those articles are about dungeon/level generation, as specific to roguelikes, but easily adaptable to your medium. Just be creative.

I especially like "Abstract Dungeons"; it specifies how to divide level generation into several distinct steps, letting you add huge amounts of flexibility in each one.

Ended upp using mainly concepts from this article. Thanks a bunch. The dungeons are a lot more fun now.