Maybe I am way off topic, but I'll try and see if anyone knows a solution, or some suggestions to start with, for my programming problem.
In my educational game I create many puzzles with electrical circuits. Now I am up to something more generic and new. Off course to share with the community, once it works :D
The latest puzzles I designed allow the player to connect any two contacts out of a total of "IntMaxContacts" contacts. Goal is to adjust the current between some of the contacts in such a way that an electric lock can be opened.
Now I have to set up Kirchoffs equations for all possible connections between two points.
My question:
I am looking for an algoritm to list all the possible closed circuits (triangles, squares, pentagons etc) in my field of a number of "IntMaxContacts" contacts.
Example:
If I have 6 contact points, numbered 1 to 6, I can make the following circuits:
123 1234 12345 123456
124 234 1235 2345 12346
125 235 345 1236 2346 3456
126 236 356 456 12356
1245
134 1246 2356 12456
135 245 13456
136 246 356 1256
23456
145 1345
146 256 1346 2456
156 1456
These loops represent all the possible single circuits to be made in my 6 point contact field.
I am looking for a way to create this list dynamically, for a given set of contactpoints.
I am sure that the code can be very elegant (maybe with nested function?), but cannot see it; being a simple physics teacher rather than a programmer :-()
Does anyone have any suggestions how to program that?
I am not familiar with the arrays and dynamic looping...
From this I must create the matrix for the kirchoff equations. The equations will be somewhat like
Example:
for the 123 circuit: I12*R12 +I23*R23 + I31*R31 = 0;
for the 2356 circuit: I23*R23 + I35*R35 + I56*R56 - I62*R62 = 0;
Convention: current's positive way: from low contact to high contact.
so the equations become:
for the 123 circuit: I12*R12 +I23*R23 - I13*R31 = 0;
for the 2356 circuit: I23*R23 + I35*R35 + I56*R56 - I26*R62 = 0;
I will define all the R values (some may be changed by the player, creating new contacts) and calculate the currents using a Gauss Jordan algoritm in a dll.
Can anyone help me with some suggestiosn to start with?
Regards,
Martijn
This is normally done with recursion, like so:
void add_point_recurse(char *loopStack, int startNum, int endNum, int desiredLoopLen)
{
int loopLen = strlen(loopStack);
int numLeft = desiredLoopLen - loopLen;
if (!numLeft)
{
printf("%s\n", loopStack);
}
else
{
for (int i = startNum; i <= endNum - (numLeft - 1); ++i)
{
// push onto stack
loopStack[loopLen] = '0' + (char) i;
loopStack[loopLen + 1] = 0;
// recurse
add_point_recurse(loopStack, i + 1, endNum, desiredLoopLen);
// pop from stack
loopStack[loopLen] = 0;
}
}
}
static int const maxLoop = 6;
main
{
int minLoop = 3;
char loopStack[maxLoop + 1];
loopStack[0] = 0;
for (int loopLen = minLoop; loopLen <= maxLoop; ++loopLen)
{
add_point_recurse(loopStack, 1, maxLoop, loopLen);
}
}
Unfortunately, AGS scripting doesn't do recursion and this is not tail-recursive so it requires some care to make it work in AGS. Basically, you have to emulate the processor stack, and use a while loop pushing "recursive calls" onto the stack and popping them off to execute until the stack is empty.
There's probably some clever trick for generating these groups of sequences using their combinatorial properties. But I can't see it off hand.
// AGS code
void add_point_recurse(String loopStack, int startNum, int endNum, int desiredLoopLen) {
int numLeft = desiredLoopLen - loopStack.Length;
if (!numLeft) Display("%s[", loopStack);
else {
int i = startNum;
while (i <= (endNum - (numLeft - 1))) {
loopStack = loopStack.AppendChar('0' + i);
add_point_recurse(loopStack, i + 1, endNum, desiredLoopLen);
loopStack = loopStack.Truncate(loopStack.Length - 1);
i++;
}
}
}
function game_start() {
int minLoop = 3;
int maxLoop = 6;
String loopStack = "";
int loopLen = minLoop;
while (loopLen <= maxLoop) {
add_point_recurse(loopStack, 1, maxLoop, loopLen);
loopLen++;
}
}I don't know why Steve said AGS doesn't allow recursion. It does...but IIRC you can only put 14 function calls into the stack at once. Not sure if that's enough for your needs, but the above code is the AGS equivalent of Steve's code. I can't really guarantee that it works exactly as Steve intended as...I don't completely understand what the code is intended to achieve...but it gives me the following output:
123 234 1246 3456
124 235 1256 12345
125 236 1345 12346
126 345 1346 12356
134 346 1356 12456
135 456 1456 13456
136 1234 2345 23456
145 1235 2346 123456
146 1236 2356
156 1245 2456
So in short...(now that I've compared the output to what you asked for) yes...I'd say that does exactly what you were looking for. In AGS code and everything. Now you may want to change that "Display" to something more suitable to your cause...storing the data into variables in the script instead of just displaying them to the user. If you need more help along those lines, that's simple stuff. Now that Steve went and did all the work! :=
BTW, put this into your global script. The part under "game_start" should go inside the game_start function in the script (between the curly braces ;)).
Man, this is great!
Thank you so much!
I'll study the script to learn from it. And I'll incorporate it in the puzzles.
Probably stumbling over some new problems, but I'll keep you informed ;-)
thanks again,
Martijn
You may also want to google for "graph searching algorithms"
I took a look, but it seems quite scientific. Not specially aiming at solving electrical circuits I think..
About the implementation; a few hints might be helpfull.
I do not see how to transpone the arrays from the algoritm in the matrix...
The next step I must take is to put the found arrays in a matrix format.
I can give an example for a few loops, let's say 123, 124, and 125. This is NOT a complete exmaple, the euqations are not enough to really sole the example values, but to get an idea of the apporach it is sufficient.
eg. The arrays represent current loops created by Conns (each with specific restance properties R; set by the gameplay)
123 => Conn12 -Conn23-Conn31
124 => Conn12 -Conn24-Conn41
125 => Conn12 -Conn25-Conn51
In each Conn a current flows:
eg in Conn12, I12 flows
To solve the currents in the circuits, I must solve a set of equations:
I12*Conn12.R + I23*Conn23.R - I13*Conn31.R = 0
I12*Conn12.R + I24*Conn24.R - I14*Conn41.R = 0
I12*Conn12.R + I25*Conn25.R - I15*Conn51.R = 0
(minus signs are because agreement made is to define all currents flowing from 'low' Conn to a 'high' Conn as positive; since these are flowing the other way around, they get the minus sign)
In matrix notation (I use the soleLinearEquation.dll), I can set this up, with 7 columns for:
I12 I13 I14 I15 I23 I24 I25
(C12.R -C13.R C23 )(I12) = 0
(C12.R -C14.R C24.R )(I13) = 0
(C12.R -C15.R C25.R )(I14) = 0
( etc etc etc )(I15) = 0
( etc etc etc )(I23) = 0
( etc etc etc )(I24) = 0
( etc etc etc )(I25) = Emf
(example covers only the first three euqations!!)
CreateMatrix(NumCols);
SetMatrixValue(1, 1, Conn12.R );
SetMatrixValue(1, 2, -1 * Conn13.R);
SetMatrixValue(1, 3, 0);
SetMatrixValue(1, 4, 0 );
SetMatrixValue(1, 5, Conn23.R);
SetMatrixValue(1, 6, 0);
SetMatrixValue(1, 7, 0);
SetMatrixValue(2, 1, Conn12.R );
SetMatrixValue(2, 2, 0);
SetMatrixValue(2, 3, -1 * Conn14.R);
SetMatrixValue(2, 4, 0 );
SetMatrixValue(2, 5, 0);
SetMatrixValue(2, 6, Conn24.R);
SetMatrixValue(2, 7, 0);
SetMatrixValue(3, 1, Conn12.R );
SetMatrixValue(3, 2, 0);
SetMatrixValue(3, 3, 0);
SetMatrixValue(3, 4, -Conn15.R );
SetMatrixValue(3, 5, 0);
SetMatrixValue(3, 6, 0);
SetMatrixValue(3, 7, Conn25.R);
SetVectorValue(1, 0);
SetVectorValue(2, 0);
SetVectorValue(3, 0);
Solve(); //solveLineaiequation Command
//IN THIS EXAMPLE ARE TOO LITTLE EQUATION TO BE ABLE TO SOLVE THE SET.
//IT IS ONLY AN EXAMPLE OF THE SYNTAX
//save the results in an array
current[0] = GetValue(1); //I12
current[1] = GetValue(2); //I13
current[2] = GetValue(3); //I14
current[3] = GetValue(4); //I15
current[4] = GetValue(5); //I23
current[5] = GetValue(6); //I24
current[6] = GetValue(7); //I15
The whole puzzles works as follows.
Player sees a filed of connectors and can draw lines from one connector to the other.
All connections are definded with a high resistance so ConnXY.R = 1000000.
When a line is drawn, the corresponding ConnXY.R is set to 1.
After a line is drawn, the Kirchoff matrix is calculated, and consequences are shown (brighter light, moving magnets etc.)
For the connections of the batteries an internal resistance is defined, and in the matrix calculations the EMF is included (not shown in the example above)