Jacky Luk

Thanks buddy...
Jack

Tushar Goel wrote:I dont think you can do this way. Probably you need store them in some collection and each time you are adding any element into it,
you need to compare that with all the values present the map.

So then I need to use a Map of ArrayList instead?
Thanks
Jack

Let's say I had 4 agents, which possess some values.
So In the first step, I consider using a Map
Then for all agents, all of these values must be unique
So
Agent 1
1,3,5
Agent 2
2,4,7
Agent 3
8,9,10
Agent 4
6,11,12
etc

But I just can't do the following
private Map<Integer, SortedSet<Nodes>> setOfNodes = new TreeMap<Integer, TreeSet<Nodes>>();
I wonder what is the correct way of doing it?
Thanks a lot
Jack

Okay, I've solved that

private static final Comparator<Node2> bcomparator = new Comparator<Node2>() { public int compare(Node2 one, Node2 two) { if (one.x == two.x && one.z == two.z) return 0; if ((one.x == two.x && one.z >= two.z) || (one.x > two.x && one.z >= two.z) || (one.x > two.x && one.z <= two.z)) return 1; if ((one.x == two.x && one.z <= two.z) || (one.x < two.x && one.z <= two.z) || (one.x < two.x && one.z >= two.z)) return -1; return 0; } };

package raft.ai.path.coop; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.SortedSet; import java.util.TreeSet; import raft.ai.path.coop.AStar2.Node2; public class Unit { private static final Comparator<Node2> bcomparator = new Comparator<Node2>() { public int compare(Node2 one, Node2 two) { if (one.x == two.x && one.z == two.z) return 0; return (one.getId() < two.getId()) ? -1 : 1; } }; private static int lastId = 0; public int order = 0; private static synchronized final int nextId() { return lastId++; } public final int id = nextId(); PathPoint2 finalDestination = null; PathPoint2 destination = null; boolean moving = false; int idleWindow = 0; AStar2.Node2 backup = null; private SortedSet<Node2> backupNodes = new TreeSet<Node2>(bcomparator); private List<PathPoint2> astarpath = new ArrayList<PathPoint2>(); private int x = 0; private int z = 0; private int t = 0; private int pathIndex = 0; private final List<PathPoint> path = new ArrayList<PathPoint>(); /** Creates a new instance of Unit */ public Unit() { } public void setLocation(int x, int z) { this.x = x; this.z = z; } public PathPoint2 getLocation() { return new PathPoint2(x, z, t); } int getPathIndex() { return pathIndex; } boolean reached() { return (x == finalDestination.x) && (z == finalDestination.z); } public void next() { pathIndex++; if (pathIndex < path.size()) { PathPoint location = path.get(pathIndex); setLocation(location.x, location.z); } } public void setDestination(int destX, int destZ, int time) { this.destination = new PathPoint2(destX, destZ, time); } public PathPoint2 getDestination() { return destination; } public PathPoint2 getFinalDestination() { return finalDestination; } public void setFinalDestination(int destX, int destZ, int time) { this.finalDestination = new PathPoint2(destX, destZ, time); } // delay for this because it is not the turn for this agent window void setPath(List<PathPoint> path) { this.path.clear(); this.path.addAll(path); System.out.println("SetPath Okay!"); // count from the current spot this.pathIndex = 0; if (! path.isEmpty()) { PathPoint location = path.get(0); setLocation(location.x, location.z); } } List<PathPoint> getPath() { return Collections.unmodifiableList(path); } public int hashCode() { return id; } public boolean equals(Object o) { return (o instanceof Unit) ? equals((Unit)o) : false; } public boolean equals(Unit other) { return this.id == other.id; } public String toString() { return "Unit: " + id; } void AddBackupNodes(SortedSet<Node2> nodes) { backupNodes.addAll(nodes); } List<Node2> GetBackupNodes() { List<Node2> lpp = new ArrayList<Node2>(); lpp.addAll(backupNodes); return lpp; } void SetAStarPath(List<PathPoint2> path) { astarpath = path; } List<PathPoint2> GetAStarPath() { return astarpath; } void clearAStarNodes() { backupNodes.clear(); astarpath.clear(); } static class PathPoint { public final int x; public final int z; public final long t; public float f; public float g; public float h; public PathPoint(NodePool.Node node) { this(node.x, node.z, node.t); } public PathPoint(int x, int z, long t) { this.x = x; this.z = z; this.t = t; } public boolean isSamePlace(PathPoint other) { return (this.x == other.x) && (this.z == other.z); } } } package raft.ai.path.coop; import java.util.ArrayList; import java.util.BitSet; import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.SortedSet; import java.util.TreeSet; import raft.kilavuz.runtime.NoPathException; public class AStar2 { private static final boolean DEBUG = false; public static final boolean USE_BITSET = true; public static final boolean USE_INTSET = false; private static final Comparator<Node2> comparator = new Comparator<Node2>() { public int compare(Node2 one, Node2 two) { if (one.id == two.id) return 0; if (one.f < two.f) return -1; if (one.f > two.f) return 1; return (one.id < two.id) ? -1 : 1; } }; private final SortedSet<Node2> openList = new TreeSet<Node2>(comparator); private static Grid grid; private final BitSet bitSetClosedList = new BitSet(1024); private final SortedSet<Integer> intSetClosedList = new TreeSet<Integer>(); private final boolean useBitSet; public AStar2(Grid g) { this(USE_BITSET, g); } public AStar2(boolean useBitSet, Grid g) { this.useBitSet = useBitSet; this.grid = g; } public synchronized Path2 findPath(Node2 from, Node2 to, Unit unit) throws NoPathException { if (unit == null) throw new NullPointerException("context is null"); unit.clearAStarNodes(); try { Node2 current = null; openList.clear(); if (useBitSet) bitSetClosedList.clear(); else intSetClosedList.clear(); int maxOpenSize = 0; from.transition = null; from.h = from.getActualTimelessCost(to); if (from.h < 0) throw new NoPathException("initial cost: " + from.h); from.g = 0; from.f = from.h; openList.add(from); while (! openList.isEmpty()) { unit.AddBackupNodes(openList); current = openList.first(); if (! openList.remove(current)) assert false; // find nodes in open list till it is exhausted if (useBitSet) { bitSetClosedList.set(current.id); } else { intSetClosedList.add(current.id); } if (current.x == to.x && current.z == to.z) { float totalCost = current.g; List<AStar2.Transition2> transitions = new ArrayList<AStar2.Transition2>(); while (current.transition != null) { transitions.add(0, current.transition); current = current.transition.fromNode(); } return new AStar2.Path2(from, transitions, totalCost); } if (DEBUG) System.out.println("current " + current + ", g: " + current.g + ", h: " + current.h + ", f: " + current.f + " parent: " + ((current.transition == null) ? null : current.transition.fromNode())); for (Transition2 transition : current.getTransitions()) { float cost = transition.getCost(unit); if (cost < 0) continue; // new a node out, id will not be the same, so a new node is produced Node2 neighbour = transition.toNode(); if (useBitSet) { if (bitSetClosedList.get(neighbour.id)) continue; } else { if (intSetClosedList.contains(neighbour.id)) continue; } if (openList.contains(neighbour)) { // check if this path is better if (current.g + cost < neighbour.g) { if (!openList.remove(neighbour)) assert false; neighbour.transition = transition; neighbour.g = current.g + cost; neighbour.f = neighbour.g + neighbour.h; openList.add(neighbour); if (DEBUG) System.out.println("updated " + neighbour + ", g: " + neighbour.g + ", h: " + neighbour.h + ", f: " + neighbour.f + " parent: " + neighbour.transition); } } else { // if neighbour in openList neighbour.transition = transition; neighbour.g = current.g + cost; neighbour.h = neighbour.getActualTimelessCost(to); neighbour.f = neighbour.g + neighbour.h; openList.add(neighbour); if (DEBUG) System.out.println("\tadded " + neighbour + ", g: " + neighbour.g + ", h: " + neighbour.h + ", f: " + neighbour.f + " parent: " + neighbour.transition); } // if-else neighbour in openList if (DEBUG) { if (openList.size() > maxOpenSize) maxOpenSize = openList.size(); } } } } finally {} throw new NoPathException(); } public SortedSet<Node2> getOpenList() { return Collections.unmodifiableSortedSet(openList); } public SortedSet<Integer> getClosedList() { if (useBitSet) { SortedSet<Integer> result = new TreeSet<Integer>(); for (int i=bitSetClosedList.nextSetBit(0); i>=0; i=bitSetClosedList.nextSetBit(i+1)) result.add(i); return Collections.unmodifiableSortedSet(result); } else { return Collections.unmodifiableSortedSet(intSetClosedList); } } /** result of a successfull path find attempt */ public class Path2 { /** first node in path */ public final Node2 startNode; /** transitions to next nodes in path */ public final List<Transition2> transitions; /** more information about pathfinding enviroment */ // public final PathContext context; // /** actual cost of this path */ public final float cost; private Path2(Node2 startNode, List<Transition2> transitions, float cost) { this.startNode = startNode; // this.context = context; this.cost = cost; this.transitions = Collections.unmodifiableList(transitions); } public String toString() { return "path, cost: " + cost + ", " + transitions; } } /** base class of all A* nodes */ public static class Node2 { private static final long serialVersionUID = 1; private static int lastId = 0; private static synchronized int nextId() { return lastId++; } /** id of this node, assigned during creation */ private final int id = nextId(); public int x; public int z; private float f; private float g; private float h; /** transition that leads to this node */ //private transient Transition transition; private Transition2 transition; /** only subclasses may call this constructor */ public Node2(int x, int z) { this.x = x; this.z = z; } /** returns id of this node. id's are assigned during creation of nodes. */ public final int getId() { return id; } private List<AStar2.Transition2> transitions; /** returns a collection of transitions from this node. * if an adjacent node is unreachable result may contain it * with a negative cost */ public Collection<Transition2> getTransitions() { if (transitions == null) { transitions = new ArrayList<AStar2.Transition2>(); for (Grid.Node node : grid.getNeighbours(x, z)) { transitions.add(new AStar2.Transition2(this, new AStar2.Node2(node.x, node.y))); } // wait transitions.add(new AStar2.Transition2(this, new AStar2.Node2(x, z))); } return transitions; } /** returns the cost estimate from this node to destination node. * if cannot be estimated, returning 0 will also result in finding a solution * but generally should take much time */ public float getActualTimelessCost(Node2 dest) { AStar2.Node2 node = dest; return grid.getActualCost(x, z, node.x, node.z); } public float getInfiniteCost() { return 9999999.9f; } //public float getF() { return f; } public float getG() { return g; } public float getH() { return h; } public float getF() { return f; } } /** a transition between two nodes */ public static class Transition2 { Node2 fromNode = null; Node2 toNode = null; private Transition2(Node2 fromNode, Node2 toNode) { this.fromNode = fromNode; this.toNode = toNode; } public AStar2.Node2 fromNode() { return fromNode; } public AStar2.Node2 toNode() { return toNode; } public float getCost(Unit unit) { return 1; } @Override public String toString() { //return "tr: " + fromNode + " - " + toNode; return "tr to: " + toNode; } } }

Thanks Pawel for your kindred help
Jack

Paweł Baczyński wrote:Your new comparator can never return a negative value.

So it violates this rule:
The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

What do you mean by repeated node? A node with the same coordinates as some other node?

Yes, not sure why there can be 2 nodes in the SortedSet with the same x and z coordinates.
the g values can be don't-care
Thanks
Jack

Hi Pawel,

I haven't got this working yet like this.

private static final Comparator<Node2> bcomparator = new Comparator<Node2>() { public int compare(Node2 one, Node2 two) { if (one.getId() == two.getId() || (one.x == two.x && one.z == two.z)) return 0; else return 1; } };
There are still repeated nodes....
Thanks
Jack

private static final Comparator<AStar2.Node2> bcomparator = new Comparator<AStar2.Node2>() { public int compare(AStar2.Node2 one, AStar2.Node2 two) { if (one.getId() == two.getId() || (one.x == two.x && one.z == two.z)) return 0; if (one.getG() < two.getG()) return -1; if (one.getG() > two.getG()) return 1; return (one.getId() < two.getId()) ? -1 : 1; } }; private SortedSet<AStar2.Node2> backupNodes = new TreeSet<AStar2.Node2>(bcomparator);

I've added some nodes to the SortedSet, in theory, the SortedSet shouldn't contain duplicate nodes
on my map, but the result isn't it. Why? There are still duplicate nodes on the map.
From each iteration of the function where it starts to add nodes to this SortedSet,
it even has been cleared as well. But I don't think I will make a difference.
Just wondering why are there duplicate nodes in my map?
Could anyone please lend me a hand?
Thanks
Jack

Stephan van Hulst wrote:If the key of the map is unrelated to the id of the unit, then you can't do this with your map. You should use different keys, or sort your values at a later stage.

Got it, thanks... I'll try the other way round.
Jack

private static final Comparator<String> comparator = new Comparator<String>() { public int compare(String one, String two) { } }; private final SortedMap<String, Unit> reserved = new TreeMap<String, Unit>(comparator);

I'd like to sort by Unit id first (where Unit has an id which is an Integer), then sort by the String value
The String values have the format of 0:0:0 where 0s are integers.
Thanks
Jack

I want to shuffle the keys within this data structure along with the values


private Map<Integer, List<Unit>> window = new TreeMap<Integer, List<Unit>>();

I can shuffle a list like this
List<Unit> remainingUnits = new ArrayList<Unit>(units.values()); Collections.shuffle(remainingUnits);

But How do I do the same for the Map container?
Thanks a lot
Jack

dodgedLoc should not be changing.
But for the backup path, there will be something added to it every now and again.
How to avoid dodgedLoc to change when the backup path is changed also.
The container is by reference, how can I just make a copy of it?
Thanks
Jack

SortedSet<NodePool.Node> backups = unit.GetBackupPath(); dodgedLoc.put(unit.id, backups.first());

Hello there,
I have changed to String as keys, and it works well.
But I've got a new question.
How do I design the algorithm such as the following happens
0:1:1 0:1:1 - clashed 0:1:2 - not clashed 1:1:1 - not clashed 2:1:1 - not clashed
I can use a SortedSet for that, but now I want to count how many occurrencies happen
for 1:1, 1:2 etc after the Set has been filtered. (The second and the third keys)
How can I do that?
Thanks
Jack

Map<Unit.PathPoint2, Integer> occurrencies = new HashMap<Unit.PathPoint2, Integer>(); for (Unit.PathPoint2 word : blockedTiles) { occurrencies.put(word, occurrencies.containsKey(word) ? occurrencies.get(word) + 1 : 1); } for (Entry<Unit.PathPoint2, Integer> entry : occurrencies.entrySet()) { System.out.println("PathPoint: "+ entry.getKey().x + " " + entry.getKey().z + " " + ", occurences: "+ entry.getValue()); }
All occurrencies happen to be one only no matter they have repeated several times.
Any ideas why?
Thanks
Jack

<s:Envelope xmlns:a="http://www.w3.org/2005/08/addressing" xmlns:s="http://www.w3.org/2003/05/soap-envelope"> <s:Header> <a:Action s:mustUnderstand="1">http://tempuri.org/IEmpService/UserLogin</a:Action> <a:MessageID>urn:uuid:0b6ad865-f1f9-4699-b20c-4ef28e6d45c7</a:MessageID> <a:ReplyTo> <a:Address>http://www.w3.org/2005/08/addressing/anonymous</a:Address> </a:ReplyTo> </s:Header> <s:Body> <UserLogin xmlns="http://tempuri.org/" /> </s:Body> </s:Envelope>

I want to mock this using one of HttpURLconnection, HttpPost of this sort....
How can I do that?
Any examples?
Thanks
Jack