Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.ArtificialAnt/3.3/AntInterpreter.cs @ 3338

Last change on this file since 3338 was 3338, checked in by gkronber, 12 years ago

Fixed bugs related to dynamic symbol constraints with ADFs. #290 (Implement ADFs)

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