Tanpohp

Archive for May, 2011

Feldtag der Landwirtschaftlich Gärtnerischen Fakultät der HU Berlin

by on May.30, 2011, under Photography

Download: Feldtag

Comments Off on Feldtag der Landwirtschaftlich Gärtnerischen Fakultät der HU Berlin :, , more...

LogfileSplitter – a small tool for splitting logfiles

by on May.16, 2011, under ByTheWay, Tools

Kürzlich wurde ich von einem Freund gebeten ein kleines Programm zu schreiben, welches in der Lage ist, große Logdatein eines Programms zu splitten um diese besser auswerten zu können.   Getest habe ich das Programm an einer 7MiB großen Logdatei mit knapp 125000 Zeilen. Das Programm splittet die Datei in 169 Dateien innerhalb von knapp 25 Sekunden, was natürlich start von dem Suchstring abhängt.

Die Logdateien werden in ein vorher gewählten Ordner geschrieben und mit ein Präfix versehen. Die Analyse findet den Suchstring mittels der Methoden: Is, Contains, BeginsWith, EndWith.

logfilesplitter gui screenshot

Scrrenshot of the LogfileSplitter V0.51

Download: LogfileSplitter

Comments Off on LogfileSplitter – a small tool for splitting logfiles :, , , , , more...

A* Algorithmus

by on May.12, 2011, under Snippets

Zur Zeit belege ich ein Fach names “AI for Games” in welchem es darum geht möglichst intelligente Programm zu schreiben. Eine der Aufgaben war einen Agent über ein Feld zu seinem Ziel zu schicken. Als Hilfestellung gab es einen Graphen der für die Navigation genutzt werden sollte, indem für diesen Graphen der A* Algorithmus implementiert werden sollte. Diese Implementation ist weiter unten zu sehen, jedoch verwendet die Wegfindung nicht zwangsweise den Algorithmus. Falls der Weg auch ohne den Graph gefunden werden kann, wird auf dieen verzichtet. Dabei durchläuft der Code folgende Schritte:

  1. Suche im Graph einen Knoten, welchem dem Startpunkt am nächsten ist und direkt einsehbar ist (nicht hinter einer Mauer).
  2. Suche im Graph einen Knoten, welchem dem Zielpunkt am nächsten ist und direkt einsehbar ist (nicht hinter einer Mauer).
  3. Wenn Start- und Zielknoten die selben sind, prüfe ob Ziel direkt einsehbar.
  4. Wenn Ja, laufe zum Zielpunkt.
  5. Wenn Nein
    1. Benutze A* um Weg zu generieren
    2. Laufe zum Startknoten
    3. Laufe Entlang des Graphen zum Zielknoten
    4. Laufen zum Zielpunkt.

Der Algorithmus hat in der Implementation eine kleine Abweichung. Der Agent läuft nicht bis zum jeweils nächsten Knoten, sondern orientiert sich um sobald dieser in der Nähe des Knotens ist. In dem folgenden Video kann man dies daran erkennen, dass der Agent vor dem Knoten abbiegt:

Die Implementation des A* in Java:

public class AStarAlgorithm {

	Graph graph;
	PriorityQueue notYetVisited;

	public AStarAlgorithm (Graph graph){
		this.graph = graph;
	}

	public Queue SearchPath(Node start, Node aim){
		notYetVisited = new PriorityQueue(64, new NodeCostComperator(SortMode.ASCENDING));
		notYetVisited.addAll(graph.GetNodes());

		//set cost to maximum and predecessor to null
		PrepareGraph(notYetVisited);
		//System.out.println();
		//System.out.println(graph.toString());
		Node currentNode = start;
		currentNode.SummedCosts = CalculateDistance(currentNode, aim);
		currentNode.SummedRealCosts = 0;
		//walk through all nodes until aim is reached
		while(currentNode != aim){
			notYetVisited.remove(currentNode);
			ExpandGraph(currentNode, aim);
			currentNode = notYetVisited.peek();
			System.out.println();
			//System.out.println(graph.toString());
		}
		//reconstruct path from aim
		return ReconstructPath(aim);
	}

	/**
	 * The resulted list of nodes is inverted.
	 * @param aim
	 * @return
	 */
	private PriorityQueue ReconstructPath(Node aim) {
		PriorityQueue result = new PriorityQueue(16,new NodeRealCostComperator(SortMode.ASCENDING));
		Node currentNode = aim;
		while(currentNode.Predecessor != null){
			//System.out.println(currentNode.Index);
			result.add(currentNode);
			currentNode = currentNode.Predecessor;
		}
		//finally add start point
		result.add(currentNode);
		return result;
	}

	private void PrepareGraph (Collection nodes){
		for(Node node : nodes){
			node.SummedCosts = Double.MAX_VALUE;
			node.SummedRealCosts = 0;
			node.Predecessor = null;
			node.PresentationColor = Color.GRAY;
		}
	}
	private void ExpandGraph (Node currentNode, Node aim){
		//System.out.println("Node: "+currentNode.Index+" =>");
		Iterator
 outLinks = currentNode.GetOutboundLinks();
		while(outLinks.hasNext()){

			Link link = outLinks.next();
			Node destination = link.GetDestination();
			if(currentNode.Predecessor == destination) continue;

			double cost = currentNode.SummedRealCosts + link.Cost + CalculateDistance(destination, aim);
			//System.out.println("          "+destination.Index+": "+currentNode.SummedRealCosts + " + " +link.Cost+" + "+CalculateDistance(destination, aim)+" = "+cost);
			if(cost < destination.SummedCosts) {
				destination.SummedRealCosts = currentNode.SummedRealCosts + link.Cost;
				destination.SummedCosts = destination.SummedRealCosts + CalculateDistance(destination, aim);
				destination.Predecessor = currentNode;
				//this ensures that queue is sorted correctly
				notYetVisited.remove(destination);
				notYetVisited.add(destination);
			}
		}
	}
	private double CalculateDistance(Node currentNode, Node aim){
		return currentNode.Coordinate.distance(aim.Coordinate);
	}
}
Comments Off on A* Algorithmus :, , , more...

Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Visit our friends!

A few highly recommended friends...