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