Help in technical programming

spook1 · Thu 31/05/2007 21:25:35

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

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

Kweepa · Fri 01/06/2007 03:33:53

This is normally done with recursion, like so:

Code: ags


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.

monkey0506 · Fri 01/06/2007 07:23:15

Code: ags

// 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

).

spook1 · Fri 01/06/2007 08:53:31

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

SSH · Fri 01/06/2007 10:33:05

You may also want to google for "graph searching algorithms"

spook1 · Sat 02/06/2007 12:21:39

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:

Code: ags




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)

Help in technical programming

spook1

Kweepa

monkey0506

spook1

SSH

spook1