Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.GeneticProgramming/3.3/ArtificialAnt/Interpreter.cs @ 12911

Last change on this file since 12911 was 12911, checked in by gkronber, 7 years ago

#2472: created project structure for HeuristicLab.Problems.GeneticProgramming and added implementations of ArtificialAnt and LawnMower

File size: 6.5 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.Data;
26using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
27
28namespace HeuristicLab.Problems.GeneticProgramming.ArtificialAnt {
29  public class Interpreter {
30
31    public int MaxTimeSteps { get; private set; }
32    public int FoodEaten { get; private set; }
33    public BoolMatrix World { get; private set; }
34
35    public ISymbolicExpressionTree Expression { get; private set; }
36
37
38    public int ElapsedTime { get; set; }
39    private int currentDirection;
40    private int currentAntLocationRow;
41    private int currentAntLocationColumn;
42    private int nFoodItems;
43    private Stack<ISymbolicExpressionTreeNode> nodeStack = new Stack<ISymbolicExpressionTreeNode>();
44
45    public Interpreter(ISymbolicExpressionTree tree, BoolMatrix world, int maxTimeSteps) {
46      this.Expression = tree;
47      this.MaxTimeSteps = maxTimeSteps;
48      // create a clone of the world because the ant will remove the food items it can find.
49      World = (BoolMatrix)world.Clone();
50      CountFoodItems();
51    }
52
53    private void CountFoodItems() {
54      nFoodItems = 0;
55      for (int i = 0; i < World.Rows; i++) {
56        for (int j = 0; j < World.Columns; j++) {
57          if (World[i, j]) nFoodItems++;
58        }
59      }
60    }
61
62    public void AntLocation(out int row, out int column) {
63      row = currentAntLocationRow;
64      column = currentAntLocationColumn;
65    }
66
67    public int AntDirection {
68      get { return currentDirection; }
69    }
70
71    public void Run() {
72      while (ElapsedTime < MaxTimeSteps && FoodEaten < nFoodItems) {
73        Step();
74      }
75    }
76
77    public void Step() {
78      // expression evaluated completly => start at root again
79      if (nodeStack.Count == 0) {
80        nodeStack.Push(Expression.Root.GetSubtree(0).GetSubtree(0));
81      }
82
83      var currentNode = nodeStack.Pop();
84      if (currentNode.Symbol.Name == "Left") {
85        currentDirection = (currentDirection + 3) % 4;
86        ElapsedTime++;
87      } else if (currentNode.Symbol.Name == "Right") {
88        currentDirection = (currentDirection + 1) % 4;
89        ElapsedTime++;
90      } else if (currentNode.Symbol.Name == "Move") {
91        MoveAntForward();
92        if (World[currentAntLocationRow, currentAntLocationColumn]) {
93          FoodEaten++;
94          World[currentAntLocationRow, currentAntLocationColumn] = false;
95        }
96        ElapsedTime++;
97      } else if (currentNode.Symbol.Name == "IfFoodAhead") {
98        int nextAntLocationRow;
99        int nextAntLocationColumn;
100        NextField(out nextAntLocationRow, out nextAntLocationColumn);
101        if (World[nextAntLocationRow, nextAntLocationColumn]) {
102          nodeStack.Push(currentNode.GetSubtree(0));
103        } else {
104          nodeStack.Push(currentNode.GetSubtree(1));
105        }
106      } else if (currentNode.Symbol.Name == "Prog2") {
107        nodeStack.Push(currentNode.GetSubtree(1));
108        nodeStack.Push(currentNode.GetSubtree(0));
109      } else if (currentNode.Symbol.Name == "Prog3") {
110        nodeStack.Push(currentNode.GetSubtree(2));
111        nodeStack.Push(currentNode.GetSubtree(1));
112        nodeStack.Push(currentNode.GetSubtree(0));
113      } else if (currentNode.Symbol is InvokeFunction) {
114        var invokeNode = currentNode as InvokeFunctionTreeNode;
115        var functionDefinition = (SymbolicExpressionTreeNode)FindMatchingFunction(invokeNode.Symbol.FunctionName).Clone();
116        var argumentCutPoints = (from node in functionDefinition.IterateNodesPrefix()
117                                 where node.Subtrees.Count() > 0
118                                 from subtree in node.Subtrees
119                                 where subtree is ArgumentTreeNode
120                                 select new { Parent = node, Argument = subtree.Symbol as Argument, ChildIndex = node.IndexOfSubtree(subtree) }).ToList();
121        foreach (var cutPoint in argumentCutPoints) {
122          cutPoint.Parent.RemoveSubtree(cutPoint.ChildIndex);
123          cutPoint.Parent.InsertSubtree(cutPoint.ChildIndex, (SymbolicExpressionTreeNode)invokeNode.GetSubtree(cutPoint.Argument.ArgumentIndex).Clone());
124        }
125        nodeStack.Push(functionDefinition.GetSubtree(0));
126      } else {
127        throw new InvalidOperationException(currentNode.Symbol.ToString());
128      }
129    }
130
131    private void MoveAntForward() {
132      NextField(out currentAntLocationRow, out currentAntLocationColumn);
133    }
134
135    private void NextField(out int nextAntLocationRow, out int nextAntLocationColumn) {
136      switch (currentDirection) {
137        case 0:
138          nextAntLocationColumn = (currentAntLocationColumn + 1) % World.Columns; // EAST
139          nextAntLocationRow = currentAntLocationRow;
140          break;
141        case 1:
142          nextAntLocationRow = (currentAntLocationRow + 1) % World.Rows; // SOUTH
143          nextAntLocationColumn = currentAntLocationColumn;
144          break;
145        case 2:
146          nextAntLocationColumn = (currentAntLocationColumn + World.Columns - 1) % World.Columns; // WEST
147          nextAntLocationRow = currentAntLocationRow;
148          break;
149        case 3:
150          nextAntLocationRow = (currentAntLocationRow + World.Rows - 1) % World.Rows; // NORTH
151          nextAntLocationColumn = currentAntLocationColumn;
152          break;
153        default:
154          throw new InvalidOperationException();
155      }
156    }
157
158
159    private SymbolicExpressionTreeNode FindMatchingFunction(string name) {
160      foreach (var defunBranch in Expression.Root.Subtrees.OfType<DefunTreeNode>()) {
161        if (defunBranch.FunctionName == name) return defunBranch;
162      }
163      throw new ArgumentException("Function definition for " + name + " not found.");
164    }
165  }
166}
Note: See TracBrowser for help on using the repository browser.