Path: csiph.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: "Christian H. Kuhn" <qno-news@qno.de>
Newsgroups: de.comp.lang.java
Subject: Element in TreeMap wird nicht gefunden
Date: Sun, 31 Dec 2017 11:21:22 +0100
Lines: 463
Message-ID: <fars12Fubj6U1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
X-Trace: individual.net 0fsUuEPJSqKsFyFlHehFeQtD1nh86FMxVvH+5xGBGj0cYAhLU=
Cancel-Lock: sha1:BZOGbo5pNKla2m3MSjBry/qPR2I=
X-Mozilla-News-Host: snews://news.individual.net:563
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.5.0
Xref: csiph.com de.comp.lang.java:13147

Hallo Gemeinde,

Mal wieder ein Problem, das auf einer „ganz einfachen“ Ausgangsfrage
beruht. Mein Bruder fragte mich: „Auf welchem Wege baue ich im
Browser-Spiel Travian in einem Getreidedorf alle Felder am schnellsten
auf Level n aus?“

Vereinfachende Annahmen: Die Zeit für den Ausbau selbst wird mit 0
angenommen („Goldclub“). Es gibt keine Lieferungen von außen. Es wird
nur der Rohstoff Getreide betrachtet. Sollten andere Rohstoffe benötigt
werden, werden sie aus Getreide im Verhältnis 1:1 „umgegoldet“ und
verschwinden so aus dem Modell. Andere Gebäude werden zur Zeit nicht
betrachtet (in eine spätere Erweiterung des Modells werden auch Mühle
und Bäckerei aufgenommen, die die Produktivität steigern). Die
Speicherkapazität wird mit unendlich angenommen (in eine spätere
Erweiterung des Modells werden auch Speicherbauten aufgenommen). Es
werden weder Truppen noch Angriffe betrachtet; das produzierte Getreide
wird ausschließlich durch Ausbau verbraucht.

Modellierung: Ein Knoten repräsentiert einen Zustand. Es gibt 15 Felder,
die die Level 0 bis n annehmen können. Die Felder sind beliebig
austauschbar. Der Zustand wird also durch ein int[n+1] dargestellt, bei
dem als Randbedingung die Summe der Einträge 15 sein muss. Eine Kante
repräsentiert einen Bauschritt. Ein Bauschritt erhöht genau ein Feld um
genau einen Level. Die Zeit für den Bauschritt entspricht im Modell nur
der Produktionszeit des benötigten Getreides, t = getreide /
produktivität. Mit dem Bauschritt erhöht sich die Produktivität des Dorfes.

In einem ersten Ansatz beinhaltete der Zustand auch die für alle zu
diesem Zustand führenden Bauschritte benötigte Zeit. Die Zahl der Knoten
nahm dadurch derart zu, dass die Warteschlange bei einer Breitensuche
bereits bei n=2 nicht mehr genügend Speicher fand. Eine Tiefensuche für
n=2 war in wenigen Sekunden abgeschlossen, n=3 dauerte mehrere Tage, der
angestrebte Wert n=17 war nicht zu erreichen.

Nach mehreren nicht zielführenden Versuchen erinnerte ich mich dann an
den Algorithmus von Dijkstra. Die Knoten erhalten noch den Abstand und
den Vorgänger als Felder. Zwei Knoten gelten als gleich, wenn die
enthaltenen int[] die gleichen Werte enthalten und n gleich ist.

Ich erzeuge zuerst ein TreeSet mit den möglichen Zuständen. Daher habe
ich für die Knoten equals() und compareTo() implementiert. Die Zustände
werden alle mit Abstand unendlich (ok, Double.MAX_VALUE) initialisiert.
Der Startzustand wird gelöscht und mit Abstand 0 wieder eingefügt.

Theoretisch. Praktisch wird er es nicht, obwohl ich ihn im TreeSet sehe.
Irgendwas habe ich falsch gemacht, und ich finde den Fehler nicht. Sieht
jemand mehr?

lg
QNo

Die Quellen sind auf
http://www.qno.de/gitweb/?p=qtraviancornoptimator.git;a=snapshot;h=d1393662bb73951ec59684008e9baa138522bd26;sf=tgz
oder zum direkten Lesen hier:

package de.qno.travian;

import java.util.Set;
import java.util.TreeSet;

/**
 * Performs the Dijkstra Algorithmus onto a graph of Travian Positions
to find the shortest build.
 *
 * @author QNo
 *
 */
public class QTravianDijkstra {

    private final int maxCropLevel;

    private int[] cropFieldsPerLevel;

    private Set<QTravianLightCropTown> visited;
    private TreeSet<QTravianLightCropTown> notVisited;

    /**
     * Private Constructor to avoid instantiation
     */
    public QTravianDijkstra(final int _maxCropLevel) {
        maxCropLevel = _maxCropLevel;
        visited = new TreeSet<QTravianLightCropTown>();
        notVisited = new TreeSet<QTravianLightCropTown>();
        cropFieldsPerLevel = new int[maxCropLevel + 1];
        createNextLevel(0, 0);
    }

    private void createNextLevel(final int _level, final int
_alreadyBuilt) {
        int stillToBuild = 15 - _alreadyBuilt;
        if (maxCropLevel == _level) {
            cropFieldsPerLevel[_level] = stillToBuild;
            notVisited.add(new QTravianLightCropTown(maxCropLevel,
cropFieldsPerLevel));
        } else {
            for (int i = stillToBuild; i >= 0; i--) {
                cropFieldsPerLevel[_level] = i;
                createNextLevel(_level + 1, _alreadyBuilt + i);
            }
        }
    }

    private void dijkstra(final QTravianLightCropTown _targetTown) {

    }

    public static void main(String[] args) {

        QTravianDijkstra test = new QTravianDijkstra(1);

        final QTravianLightCropTown startTown = new
QTravianLightCropTown(test.maxCropLevel);
        startTown.setStartTown();
        System.out.println(test.notVisited.contains(startTown));
        test.notVisited.remove(startTown);
        test.notVisited.add(startTown);
        int[] targetArray = new int[test.maxCropLevel + 1];
        targetArray[test.maxCropLevel] = 15;
        final QTravianLightCropTown targetTown = new
QTravianLightCropTown(test.maxCropLevel, targetArray);

        test.dijkstra(targetTown);

    } // main

} // class

=========================================================================================

package de.qno.travian;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * This class represents a village with 15 crop fields and only 1 field
of every other resource. ATM, there are no other fields or buildings
 * supported, but that might change.
 *
 * <p>
 * This implementation knows about the number of crop fields per level
and about the build moves that constructed the actual status of village.
 * </p>
 *
 * <p>
 * This implementation is not thred-safe. In normal use, thread safety
might be achievable if calls of build...(), townProductivity(),
 * isMaxDeveloped(), setAge(), getAge(), and getAllowedBuildMoves() are
synchronized by the client. Using evaluate(boolean) is thread-hostile,
because
 * it stores it’s results in static variables.
 * </p>
 *
 * @author QNo
 *
 */
public final class QTravianLightCropTown implements
Comparable<QTravianLightCropTown> {

    private static final int[] PRODUCTIVITY = { 4, 7, 13, 21, 31, 46,
70, 98, 140, 203, 280, 392, 525, 693, 889, 1120, 1400, 1820, 2240, 2800,
3430 };

    private static boolean goldClub = true;
    private static boolean hero = true;

    private transient int maxCropLevel;

    private transient int[] cropFieldsPerLevel;

    private QTravianLightCropTown predecessor;
    private double distance = Double.MAX_VALUE;

    /**
     * Public Standard Constructor. Provides a new undeveloped town.
     */
    public QTravianLightCropTown() {
        this(20);
    }

    /**
     * Public Constructor with maxCropLevel. Provides a new undeveloped
town.
     *
     * @param _maxCropLevel
     *            Level which Crop Fields are maximally developed to.
     */
    public QTravianLightCropTown(final int _maxCropLevel) {
        maxCropLevel = _maxCropLevel;

        cropFieldsPerLevel = new int[maxCropLevel + 1];
        cropFieldsPerLevel[0] = 15;
        for (int i = 1; i <= maxCropLevel; i++) {
            cropFieldsPerLevel[i] = 0;
        }

        distance = Double.MAX_VALUE;
    }

    /**
     * Public Constructor with development. Provides a developed town.
     *
     * @param _maxCropLevel
     *            Level which Crop Fields are maximally developed to.
     * @param _cropFieldsPerLevel
     *            Development status: how many fields per level.
     */
    @SuppressWarnings("PMD.UseVarargs") // Stupid proposition
    public QTravianLightCropTown(final int _maxCropLevel, final int[]
_cropFieldsPerLevel) {
        this(_maxCropLevel);

        cropFieldsPerLevel = _cropFieldsPerLevel.clone();
    }

    /**
     * Copy constructor.
     *
     * @param _original
     *            the village to copy
     */
    public QTravianLightCropTown(final QTravianLightCropTown _original) {
        this(_original.maxCropLevel);
        cropFieldsPerLevel = _original.cropFieldsPerLevel.clone();
    }

    /**
     * Calculates crop productivity of a village.
     *
     * <p>
     * This implementation uses a table of crop productivity by crop
field level and some modificators (atm goldclub only). It is given in
crop per
     * hour.
     * </p>
     *
     * @return crop productivity of this village.
     */
    private double townProductivity() {
        int actualProductivity = 0;

        for (int i = 0; i <= maxCropLevel; i++) {
            actualProductivity += cropFieldsPerLevel[i] * PRODUCTIVITY[i];
        }
        return (goldClub ? actualProductivity * 1.25 :
actualProductivity) + (hero ? 360 : 0);
    }

    /**
     * Tests if all crop fields are developed up to maxCropLevel.
     *
     * @return true, if all crop fields are developed up to
maxCropLevel; false otherwise
     */
    private boolean isMaxDeveloped() {
        return cropFieldsPerLevel[maxCropLevel] == 15;
    }

    /**
     * Gets a list of all allowed update or build actions.
     *
     * @return a list of all allowed update or build actions
     */
    private List<QTravianBuildMoves> getAllowedBuildMoves() {
        final List<QTravianBuildMoves> allowedMoves = new
LinkedList<QTravianBuildMoves>();

        for (int i = 0; i < maxCropLevel; i++) {
            if (0 != cropFieldsPerLevel[i]) {
                allowedMoves.add(QTravianBuildMoveCrop.getInstance(i));
            }
        }

        return allowedMoves;
    }

    /**
     * Executes a List of QTravianBuildMoves on this village. Build
moves are executed in the order of the list iterator.
     *
     * @param _moves
     *            a list of build moves
     */
    public void buildTown(final List<QTravianBuildMoves> _moves) {
        for (final QTravianBuildMoves move : _moves) {
            if (move instanceof QTravianBuildMoveCrop) {
                buildCropField(((QTravianBuildMoveCrop)
move).getFromLevel());
            }
        }
    }

    /**
     * Upgrades a crop field from _fromLevel by one level.
     *
     * @throws IllegalArgumentException
     *             if _fromLevel is not an int from 0 to 19.
     * @param _fromLevel
     *            the level of the crop field before updating. An int
from 0 to 19.
     */
    private void buildCropField(final int _fromLevel) {
        if (0 > _fromLevel || maxCropLevel < _fromLevel) {
            throw new IllegalArgumentException("Only Crop Builds allowed
between level 0 and " + maxCropLevel + ".");
        }
        cropFieldsPerLevel[_fromLevel]--;
        cropFieldsPerLevel[_fromLevel + 1]++;
    }

    /**
     * Getter for Distance.
     *
     * @return the distance
     */
    public double getDistance() {
        return distance;
    }

    /**
     * Setter for distance.
     *
     * @param _distance
     *            the distance to set
     */
    public void setDistance(final double _distance) {
        this.distance = _distance;
    }

    /**
     * Getter for predecessor.
     *
     * @return the predecessor
     */
    public QTravianLightCropTown getPredecessor() {
        return predecessor;
    }

    /**
     * Setter for predecessor.
     *
     * @param _predecessor
     *            the predecessor to set
     */
    public void setPredecessor(final QTravianLightCropTown _predecessor) {
        this.predecessor = _predecessor;
    }

    /**
     * Sets distance = 0, marking this town as start town for dijkstra
algorithm.
     */
    public void setStartTown() {
        distance = 0;
    }

    /**
     * Returns a brief description of this Town. The exact details of
the representation are unspecified and subject to change.
     *
     * @return a brief description
     */
    @Override
    public String toString() {
        final StringBuilder returnString = new StringBuilder(600);
        returnString.append("This town:\n   15 Corn Fields:\n");
        for (int i = 0; i <= maxCropLevel; i++) {
            if (cropFieldsPerLevel[i] > 0) {
                returnString.append("   " + cropFieldsPerLevel[i] + " of
level " + i + "\n");
            }
        }
        returnString.append("The Town needs " +
QTravianCropTown.formatToTimeDiff(distance) + " from Start Town.");
        return returnString.toString();
    }

    /*
     * (non-Javadoc)
     *
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + Arrays.hashCode(cropFieldsPerLevel);
        return result;
    }

    /*
     * (non-Javadoc)
     *
     * @see java.lang.Object#equals(java.lang.Object)
     */
    @Override
    public boolean equals(final Object _obj) {
        boolean equals = true;

        if (_obj == null) {
            equals = false;
        } else {
            if (_obj instanceof QTravianLightCropTown) {
                final QTravianLightCropTown other =
(QTravianLightCropTown) _obj;
                if (!Arrays.equals(cropFieldsPerLevel,
other.cropFieldsPerLevel) || maxCropLevel != other.maxCropLevel) {
                    equals = false;
                }
            } else {
                equals = false;
            }
        }
        return equals;
    }

    @Override
    @SuppressWarnings("PMD.AvoidThrowingNullPointerException")
    public int compareTo(final QTravianLightCropTown _obj) {
        if (null == _obj) {
            throw new NullPointerException();
        }
        int returnValue = -1;
        if (this.equals(_obj)) {
            returnValue = 0;
        } else {
            if (distance < _obj.distance) {
                returnValue = -1;
            } else if (distance > _obj.distance) {
                returnValue = 1;
            } else {
                for (int i = maxCropLevel; i < 0; i--) {
                    if (cropFieldsPerLevel[i] <
_obj.cropFieldsPerLevel[i]) {
                        returnValue = -1;
                        break;
                    } else if (cropFieldsPerLevel[i] >
_obj.cropFieldsPerLevel[i]) {
                        returnValue = 1;
                        break;
                    }
                }
            }
        }
        return returnValue;

    }

    public static void main(String... _args) {
        final QTravianLightCropTown townOne = new QTravianLightCropTown(3);
        QTravianLightCropTown townTwo = new QTravianLightCropTown(3);
        System.out.println(townOne.equals(townTwo));
        townOne.buildCropField(0);
        System.out.println(townOne.equals(townTwo));
        System.out.println(townOne.compareTo(townTwo));
        int[] arrayTwo = { 14, 1, 0, 0 };
        townTwo = new QTravianLightCropTown(3, arrayTwo);
        System.out.println(townOne.equals(townTwo));
    }
}