Connecting pieces of wires- algorithm

I'm using C#, but in the future I might need to use it on other languages.

Many games have such puzzles. There is a group of wires (there are 2 types of wires: straight and curved.), there is a place from where a signal comes and there is a place from where the signal must leave. But the arrangement of the wires doesn't allow that to happen. You must turn some of the wires in order to create a path for the signal.

Yeah, I'm trying to find the continent America again, in order not to try finding it more than once in the future.

Somewhere in the future I will also try the same thing but this time with wires that split the signal to 2 or 3 signals.

Problem is that I can't think of an algorithm that I can imagine how to turn it into a code开发者_运维知识库. I have been thinking for some time and I can't think of anything good.

So, can you help me? I will be able to understand the algorithm as "what does the program has to do", but I basically need help with understanding the algorithm as "how to write the code".

Thanks!

Take a look at some maze generation algorithms -- they do the same thing you're looking for, and as such are what you'll need to create the grid. Pick a simple 'cell-carver' from the ones I linked to; randomly rotate all of the wire-pieces, et voilà!

A comment on your question notes that turning an algorithm into code involves breaking it down bit by bit -- so that's what we'll do:

You'd start with a grid of potential wire locations (probably 2D, but a 3D game would be amazing).

To produce a solvable level, you could do a couple things -- produce a level, and see if it is solvable (bad), or produce a solved level, then "unsolve" it (better). As I alluded to above, producing a solved level involves algorithms very similar to maze generation -- a solved level would have many traversable "paths", just like a maze. Unsolving the level would just loop through all wire pieces, and rotate them a bit.

But what of maze generation? The resource I linked to contains some algorithms that would be perfect for your use -- a simple randomized DFS should be plenty for your needs.

You'll note that I covered the general case involving branching wires -- as it is, excluding branching means you have to do more coding, to "prune" branches intelligently -- that is, backtracking when your one true path gets stuck, say in a corner, due to the random movement probably necessary to make an interesting level.

You should also note that a solution for such a game would, if I understood correctly, require use of all given wire (I know some games like this). Otherwise, the game would probably be a lot simpler to play given the above generation tactics.

The Union-Find algorithms (that answer my problem) are explained in this PDF file: http://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

I don't think I would have ever thought of this algorithm, let alone making it fast.