Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.ArtificialAnt/3.4/AntInterpreter.cs @ 6428

Last change on this file since 6428 was 5809, checked in by mkommend, 14 years ago

#1418: Reintegrated branch into trunk.

File size: 6.6 KB
RevLine 
[3223]1#region License Information
2/* HeuristicLab
[5445]3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[3223]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;
[4068]23using System.Collections.Generic;
[3294]24using System.Linq;
[4068]25using HeuristicLab.Data;
[3223]26using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
[3462]27using HeuristicLab.Problems.ArtificialAnt.Symbols;
[3223]28
29namespace HeuristicLab.Problems.ArtificialAnt {
[3239]30  public class AntInterpreter {
[3338]31
[3239]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    }
[3223]43
[3239]44    private SymbolicExpressionTree expression;
45    public SymbolicExpressionTree Expression {
46      get { return expression; }
47      set {
48        expression = value;
49      }
50    }
[3338]51
52    private SymbolicExpressionTreeNode FindMatchingFunction(string name) {
[5733]53      foreach (var defunBranch in expression.Root.Subtrees.OfType<DefunTreeNode>()) {
[3338]54        if (defunBranch.FunctionName == name) return defunBranch;
55      }
56      throw new ArgumentException("Function definition for " + name + " not found.");
57    }
58
59
60
[3223]61    public int ElapsedTime { get; set; }
62    private int currentDirection;
[3239]63    private int currentAntLocationRow;
64    private int currentAntLocationColumn;
65    private int nFoodItems;
[5517]66    private Stack<ISymbolicExpressionTreeNode> nodeStack = new Stack<ISymbolicExpressionTreeNode>();
[3223]67
[3239]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      }
[3223]75    }
76
[3239]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();
[3223]89      }
90    }
91
[3239]92    public void Step() {
93      // expression evaluated completly => start at root again
[3338]94      if (nodeStack.Count == 0) {
[5733]95        nodeStack.Push(Expression.Root.GetSubtree(0).GetSubtree(0));
[3338]96      }
97
[3239]98      var currentNode = nodeStack.Pop();
[3223]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) {
[3239]106        MoveAntForward();
107        if (World[currentAntLocationRow, currentAntLocationColumn])
108          FoodEaten++;
109        World[currentAntLocationRow, currentAntLocationColumn] = false;
[3223]110        ElapsedTime++;
111      } else if (currentNode.Symbol is IfFoodAhead) {
[3239]112        int nextAntLocationRow;
113        int nextAntLocationColumn;
114        NextField(out nextAntLocationRow, out nextAntLocationColumn);
115        if (World[nextAntLocationRow, nextAntLocationColumn]) {
[5733]116          nodeStack.Push(currentNode.GetSubtree(0));
[3223]117        } else {
[5733]118          nodeStack.Push(currentNode.GetSubtree(1));
[3223]119        }
120      } else if (currentNode.Symbol is Prog2) {
[5733]121        nodeStack.Push(currentNode.GetSubtree(1));
122        nodeStack.Push(currentNode.GetSubtree(0));
[3223]123        return;
124      } else if (currentNode.Symbol is Prog3) {
[5733]125        nodeStack.Push(currentNode.GetSubtree(2));
126        nodeStack.Push(currentNode.GetSubtree(1));
127        nodeStack.Push(currentNode.GetSubtree(0));
[3223]128        return;
[3294]129      } else if (currentNode.Symbol is InvokeFunction) {
130        var invokeNode = currentNode as InvokeFunctionTreeNode;
[3343]131        var functionDefinition = (SymbolicExpressionTreeNode)FindMatchingFunction(invokeNode.Symbol.FunctionName).Clone();
[3338]132        var argumentCutPoints = (from node in functionDefinition.IterateNodesPrefix()
[5733]133                                 where node.Subtrees.Count() > 0
134                                 from subtree in node.Subtrees
[3338]135                                 where subtree is ArgumentTreeNode
[5733]136                                 select new { Parent = node, Argument = subtree.Symbol as Argument, ChildIndex = node.IndexOfSubtree(subtree) }).ToList();
[3338]137        foreach (var cutPoint in argumentCutPoints) {
[5733]138          cutPoint.Parent.RemoveSubtree(cutPoint.ChildIndex);
139          cutPoint.Parent.InsertSubtree(cutPoint.ChildIndex, (SymbolicExpressionTreeNode)invokeNode.GetSubtree(cutPoint.Argument.ArgumentIndex).Clone());
[3338]140        }
[5733]141        nodeStack.Push(functionDefinition.GetSubtree(0));
[3239]142      } else {
[3223]143        throw new InvalidOperationException(currentNode.Symbol.ToString());
144      }
145    }
146
[3239]147    private void MoveAntForward() {
148      NextField(out currentAntLocationRow, out currentAntLocationColumn);
149    }
[3223]150
[3239]151    private void NextField(out int nextAntLocationRow, out int nextAntLocationColumn) {
[3223]152      switch (currentDirection) {
153        case 0:
[3239]154          nextAntLocationColumn = (currentAntLocationColumn + 1) % World.Columns; // EAST
155          nextAntLocationRow = currentAntLocationRow;
[3223]156          break;
157        case 1:
[3239]158          nextAntLocationRow = (currentAntLocationRow + 1) % World.Rows; // SOUTH
159          nextAntLocationColumn = currentAntLocationColumn;
[3223]160          break;
161        case 2:
[3239]162          nextAntLocationColumn = (currentAntLocationColumn + World.Columns - 1) % World.Columns; // WEST
163          nextAntLocationRow = currentAntLocationRow;
[3223]164          break;
165        case 3:
[3239]166          nextAntLocationRow = (currentAntLocationRow + World.Rows - 1) % World.Rows; // NORTH
167          nextAntLocationColumn = currentAntLocationColumn;
[3223]168          break;
169        default:
170          throw new InvalidOperationException();
171      }
172    }
173  }
174}
Note: See TracBrowser for help on using the repository browser.