0
$\begingroup$

I have a game application with characters that have to cross mazes. The game can generate thousands of different mazes and the characters can move according to users choice and cross the maze manually. We needed to add the possibility to show a correct way out of each maze. Therefore we added the possiblity to move the characters according to an xml file.

This XML file is very complex, usually around thirty-fifty thousands of rows. lets say its in the following structure (but much more complex):

  <maze-solution>
  <part id="1">
  <sector number="1">
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>1250></start-position>
            <angle>23.43</angle>
            <duration>0.44</duration>
        </movement>
        <action-type>run</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>light</equipemnt>
        <movement>
            <start-position>4223></start-position>
            <angle>233.43</angle>
            <duration>0.32</duration>
        </movement>
        <action-type>walk</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>1231></start-position>
            <angle>84.134</angle>
            <duration>0.454</duration>
        </movement>
        <action-type>run</action-type>
        <character>2</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>932></start-position>
            <angle>34.43</angle>
            <duration>0.50</duration>
        </movement>
        <action-type>duck</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>   
  </sector>
  <sector number="2">
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>1250></start-position>
            <angle>23.43</angle>
            <duration>0.44</duration>
        </movement>
        <action-type>run</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>light</equipemnt>
        <movement>
            <start-position>4223></start-position>
            <angle>233.43</angle>
            <duration>0.44</duration>
        </movement>
        <action-type>walk</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>1231></start-position>
            <angle>84.134</angle>
            <duration>0.454</duration>
        </movement>
        <action-type>run</action-type>
        <character>2</character>
        <protection>none</protection>       
    </action>
    <action>
        <equipment>heavy</equipemnt>
        <movement>
            <start-position>932></start-position>
            <angle>23.43</angle>
            <duration>0.44</duration>
        </movement>
        <action-type>duck</action-type>
        <character>1</character>
        <protection>none</protection>       
    </action>   
  </sector>
  <sector number="3">   
  </maze-solution>

At the moment, we have the ability to analayze each maze using a CNN algorithm for image classification and generate an xml that represents a way out of the maze - meaning that if the characters will be moved according to that file, they will cross the maze. That algorithm has been tested and can not be changed by any means.

The problem is that most of the times the generated file is not the best one possible (and quite often it is very noticeable). There are different, faster, better ways to cross the maze.

We also have thousands (and we can get as many as needed) files that were created manually for saved mazes and therefore they are representing an elegant and a fast way out of the maze. The ideal goal is that someday, our program will learn how to generate such a file without people creating them manually.

To conclude, we have plenty of XML files generated by a program compared to the hard-coded XML files. There are thousands of pairs - The file the program generated, and the "ideal" file version that a person created. (and we can get infinite number of such pairs) Is there a way, using those thousands of pairs, to make a second step algorithm that will "learn" what adjustments should be made in the generated XML files to make them more like the hard-coded ones?

I'm not looking for a specific solution here but for a general idea that will get me going. I hope i made myself clear but if I missed some info let me know and I will add it.

$\endgroup$
  • $\begingroup$ What are some differences between the CNN generated solution and the "perfect" solution. Can these differences be grouped into categories? Can you post an example of the input xml and the "perfect" xml? $\endgroup$ – Adnan S Mar 2 '18 at 8:21
  • $\begingroup$ I edited the question, hopefully it will be helpful $\endgroup$ – user9890 Mar 2 '18 at 17:27
  • $\begingroup$ I added a suggestion below - have you also posted this on the cross-validated stack exchange? It seems to have more activity $\endgroup$ – Adnan S Mar 2 '18 at 18:36
0
$\begingroup$

So I see two parts to your problem where machine learning is appropriate.

  1. Generating a maze solution or set of possible working solutions
  2. Selecting/optimizing the best solution from part 1 above

Seems like part 1 is already addressed by you so I will share some suggestions on part 2 to explore.

If you can parse the XML file to extract elements and express them as a sequence of directions (like way old school turtle programming language) --

light, go forward 10, move 10, pick up, stop, drop, turn 10

...... then you can use the seq2seq machine learning technique to train a neural network to take semi-optimized sequences and find the the best sequence.

In other words, the seq2seq NN will be trained on pairs of sequences that consist of a non-optimal sequence and a corresponding "ideal" sequence. This is similar to neural machine translation and summarization but you are translating sequences. NN architectures that apply in this case are RNN, LSTM, etc.

Hopefully this gets you started with some exploration. I don't have personal experience with using seq2seq in this domain but this seems appropriate.

| improve this answer | |
$\endgroup$
  • $\begingroup$ it is not possible an algorithm that works only over the paths (automatic and manual) without take into account the maze description. It will generate invalid paths. $\endgroup$ – pasaba por aqui Mar 3 '18 at 12:38
  • $\begingroup$ @pasaba so how does machine translation work without being taught the grammar? The goal is NOT to translate the whole path at once but parts of the path - for example, the CNN could be generating three rights which can be replaced by one left. Perhaps a picture by OP will help. I am trying to work within the constraints of OP and you are proposing a completely new approach which is likely better but not what OP is constrained to. $\endgroup$ – Adnan S Mar 3 '18 at 19:45
  • $\begingroup$ A natural language has a single grammar, the net has a lot (millions) of valid sentences to infer it. However, in this case, for a single maze there are only a single optimal path. Imposible to infer the maze from the path. $\endgroup$ – pasaba por aqui Mar 3 '18 at 19:53
  • $\begingroup$ @pasaba - sure OK :-) I have suggested a specific algorithm to OP as he asked. $\endgroup$ – Adnan S Mar 3 '18 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy