source: stable/HeuristicLab.Problems.GeneticProgramming/3.3/LawnMower/Interpreter.cs @ 13280

Last change on this file since 13280 was 13280, checked in by gkronber, 4 years ago

#2472: merged r12921,r12936:12938,r12940,r12947,r13055:13058,r13163,r13267,r13269 from trunk to stable

File size: 6.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
26
27namespace HeuristicLab.Problems.GeneticProgramming.LawnMower {
28  public static class Interpreter {
29    private enum Heading {
30      South,
31      East,
32      North,
33      West
34    };
35
36    private class MowerState {
37      public Heading Heading { get; set; }
38      public Tuple<uint, uint> Position { get; set; }
39      public int Energy { get; set; }
40      public MowerState() {
41        Heading = Heading.South;
42        Position = new Tuple<uint, uint>(0, 0);
43        Energy = 0;
44      }
45    }
46
47    public static bool[,] EvaluateLawnMowerProgram(int length, int width, ISymbolicExpressionTree tree) {
48      bool[,] lawn = new bool[length, width];
49      var mowerState = new MowerState();
50      mowerState.Heading = Heading.South;
51      mowerState.Energy = length * width * 2;
52      lawn[mowerState.Position.Item1, mowerState.Position.Item2] = true;
53      EvaluateLawnMowerProgram(tree.Root, mowerState, lawn, tree.Root.Subtrees.Skip(1).ToArray());
54      return lawn;
55    }
56
57    private static Tuple<int, int> EvaluateLawnMowerProgram(ISymbolicExpressionTreeNode node, MowerState mowerState, bool[,] lawn, IEnumerable<ISymbolicExpressionTreeNode> adfs) {
58      if (mowerState.Energy <= 0) return Tuple.Create(0, 0);
59
60      if (node.Symbol is ProgramRootSymbol) {
61        return EvaluateLawnMowerProgram(node.GetSubtree(0), mowerState, lawn, adfs);
62      } else if (node.Symbol is StartSymbol) {
63        return EvaluateLawnMowerProgram(node.GetSubtree(0), mowerState, lawn, adfs);
64      } else if (node.Symbol.Name == "Left") {
65        switch (mowerState.Heading) {
66          case Heading.East: mowerState.Heading = Heading.North;
67            break;
68          case Heading.North: mowerState.Heading = Heading.West;
69            break;
70          case Heading.West: mowerState.Heading = Heading.South;
71            break;
72          case Heading.South:
73            mowerState.Heading = Heading.East;
74            break;
75        }
76        return new Tuple<int, int>(0, 0);
77      } else if (node.Symbol.Name == "Forward") {
78        int dRow = 0;
79        int dCol = 0;
80        switch (mowerState.Heading) {
81          case Heading.East:
82            dCol++;
83            break;
84          case Heading.North:
85            dRow--;
86            break;
87          case Heading.West:
88            dCol--;
89            break;
90          case Heading.South:
91            dRow++;
92            break;
93        }
94        uint newRow = (uint)((mowerState.Position.Item1 + lawn.GetLength(0) + dRow) % lawn.GetLength(0));
95        uint newColumn = (uint)((mowerState.Position.Item2 + lawn.GetLength(1) + dCol) % lawn.GetLength(1));
96        mowerState.Position = Tuple.Create(newRow, newColumn);
97        mowerState.Energy = mowerState.Energy - 1;
98        lawn[newRow, newColumn] = true;
99        return Tuple.Create(0, 0);
100      } else if (node.Symbol.Name == "Sum") {
101        var p = EvaluateLawnMowerProgram(node.GetSubtree(0), mowerState, lawn, adfs);
102        var q = EvaluateLawnMowerProgram(node.GetSubtree(1), mowerState, lawn, adfs);
103        return Tuple.Create(p.Item1 + q.Item1, p.Item2 + q.Item2);
104      } else if (node.Symbol.Name == "Prog") {
105        EvaluateLawnMowerProgram(node.GetSubtree(0), mowerState, lawn, adfs);
106        return EvaluateLawnMowerProgram(node.GetSubtree(1), mowerState, lawn, adfs);
107      } else if (node.Symbol.Name == "Frog") {
108        var p = EvaluateLawnMowerProgram(node.GetSubtree(0), mowerState, lawn, adfs);
109        int x = p.Item1;
110        int y = p.Item2;
111        while (x < 0) x += lawn.GetLength(0);
112        while (y < 0) y += lawn.GetLength(1);
113        var newRow = (uint)((mowerState.Position.Item1 + x) % lawn.GetLength(0));
114        var newCol = (uint)((mowerState.Position.Item2 + y) % lawn.GetLength(1));
115        mowerState.Position = Tuple.Create(newRow, newCol);
116        mowerState.Energy = mowerState.Energy - 1;
117        lawn[newRow, newCol] = true;
118        return Tuple.Create(0, 0);
119      } else if (node.Symbol is InvokeFunction) {
120        var invokeNode = node as InvokeFunctionTreeNode;
121
122        // find the function definition for the invoke call
123        var functionDefinition = (from adf in adfs.Cast<DefunTreeNode>()
124                                  where adf.FunctionName == invokeNode.Symbol.FunctionName
125                                  select adf).Single();
126        // clone the function definition because we are replacing the argument nodes
127        functionDefinition = (DefunTreeNode)functionDefinition.Clone();
128        // find the argument tree nodes and their parents in the original function definition
129        // toList is necessary to prevent that newly inserted branches are iterated
130        var argumentCutPoints = (from parent in functionDefinition.IterateNodesPrefix()
131                                 from subtree in parent.Subtrees
132                                 where subtree is ArgumentTreeNode
133                                 select new { Parent = parent, Argument = subtree.Symbol as Argument, ChildIndex = parent.IndexOfSubtree(subtree) })
134                                 .ToList();
135        // replace all argument tree ndoes with the matching argument of the invoke node
136        foreach (var cutPoint in argumentCutPoints) {
137          cutPoint.Parent.RemoveSubtree(cutPoint.ChildIndex);
138          cutPoint.Parent.InsertSubtree(cutPoint.ChildIndex, (SymbolicExpressionTreeNode)invokeNode.GetSubtree(cutPoint.Argument.ArgumentIndex).Clone());
139        }
140        return EvaluateLawnMowerProgram(functionDefinition.GetSubtree(0), mowerState, lawn, adfs);
141      } else {
142        // try to parse as ephemeral random const with format: "x,y" (x, y in [0..32[)
143        int x, y;
144        var tokens = node.Symbol.Name.Split(',');
145        if (tokens.Length == 2 &&
146            int.TryParse(tokens[0], out x) &&
147            int.TryParse(tokens[1], out y)) {
148          return Tuple.Create(x, y);
149        } else {
150          throw new ArgumentException("Invalid symbol in the lawn mower program.");
151        }
152      }
153    }
154  }
155}
Note: See TracBrowser for help on using the repository browser.