Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PersistenceSpeedUp/HeuristicLab.Problems.ArtificialAnt/3.3/AntInterpreter.cs @ 12858

Last change on this file since 12858 was 5445, checked in by swagner, 14 years ago

Updated year of copyrights (#1406)

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