[Suggestion: code fix]VisibleAreaSegment.compareTo(Object)

[LWZ]

This is code from /src/net/rptools/maptool/client/ui/zone/vbl/VisibleAreaSegment.java

Code: Select all

public int compareTo(Object o) {
	if (!(o instanceof VisibleAreaSegment)) {
		return 0;
	}
	double odist = ((VisibleAreaSegment) o).getDistanceFromOrigin();
	return getDistanceFromOrigin() < odist ? -1 : getDistanceFromOrigin() == odist ? 0 : 1;
}

The compareTo returns 0 (indicating equality) when the other object is the wrong type. The contract for compareTo specified throwing an exception in that case.

Suggested fix:

Code: Select all

public int compareTo(Object o) {
	double odist = ((VisibleAreaSegment) o).getDistanceFromOrigin();
	return getDistanceFromOrigin() < odist ? -1 : getDistanceFromOrigin() == odist ? 0 : 1;
}

Recommended fix: Change the interface to Comparable<VisibleAreaSegment> and change the code to

Code: Select all

public int compareTo(VisibleAreaSegment other) {
	double odist = other.getDistanceFromOrigin();
	return getDistanceFromOrigin() < odist ? -1 : getDistanceFromOrigin() == odist ? 0 : 1;
}

This may also reveal some typing errors at compile time, though it probably won't.

More-recommended fix: Rework the program to work in ints (such as using the SQUARES of distances) rather than doubles. Doubles means rounding errors and difficulty in comparisons when two numbers are supposed to be equal but were calculated in different ways. But I don't know what I'm talking about, because I don't know what this class is for, and it's possibly a big fix.

If you do change it, the code should be something like this:

Code: Select all

public int compareTo(VisibleAreaSegment other) {
	return getDistanceSquaredFromOrigin() - other.getDistanceSquaredFromOrigin();
}

--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

Motivation: http://imgur.com/F7WZ1

I don't know what the problem is, but might as well have this cleaned up, right? I don't think this will fix the error, though.

[Lee]

Thanks for the input. Unfortunately, at MT's stage of maturity, it's pretty much locked to the data types it's been using for years. You can do a quick check on how painful the process to change this can be by beginning refactoring to the change you propose. The sea of red which follows will indicate how large the undertaking would be.

Also, the error you encountered can be easily circumvented by setting a system property to use legacy sort instead of the TimSort algorithm Java 7 employs, which brings to attention that you're likely using b87 with Java 7 in your system, aren't you? Anyway, I do prefer the goal your approach suggested, which is to keep TimSort; however, this involves applying handling code to about 15 or so MT classes, most of which do not share the the same comparable objects (i.e. hence cannot be dumped to a single handling class, unless one is patient enough to overload/create handling for every data type needed - which I wasn't). With that being said, it's unlikely this approach will be employed the official dev team will employ for the sake of expediency, especially when one line can revert MT to what everyone has grown accustomed to.

[LWZ]

I finally figured out SVN and was looking around when I saw the change made (presumably) in response to this topic.

Code: Select all

////
// COMPARABLE
public int compareTo(VisibleAreaSegment o) {
	if (o == null)
		throw new NullPointerException("compareTo() parameter is null");

	double odist = o.getDistanceFromOrigin();
	// FJE Wouldn't it work to just use the following?
	//		return getDistanceFromOrigin() - odist;
	return getDistanceFromOrigin() < odist ? -1 : getDistanceFromOrigin() == odist ? 0 : 1;
}

Why the null comparison? o.getDi...() will already throw NullPtrExc if o is null. Is this a need for an error message?

By the way, in response to the comment, returning the difference in general won't work because it would round the float toward 0, though I guess it's fine which is fine if you don't think you will get distances that should be exactly 1 but might be a little lower due to earlier rounding errors.

Edit: So yeah, the code I originally complained about was changed in 2011. How embarrassing. I have no idea why I saw that version, since I only learned about MapTools last month.

[Azhrei]

Why the null comparison? o.getDi...() will already throw NullPtrExc if o is null. Is this a need for an error message?

I can't say for certain. I can see two reasons: explicitly programming the comparison makes it clear that the programmer has an expectation that the parameter could be null so it's a form of "defensive programming", the other reason is that the explicit throw statement allows a message to be specified that clearly delineates that the problem is a null parameter to the method (as compared to a generic NPE message).

By the way, in response to the comment, returning the difference in general won't work because it would round the float toward 0, though I guess it's fine which is fine if you don't think you will get distances that should be exactly 1 but might be a little lower due to earlier rounding errors.

Floats are not rounded to integer, they are truncated. That means that a value such as "0.1" becomes "0" and a value like "-0.1" becomes "-1".

In either case, it doesn't matter. The contract for this method only specifies that it returns -1, 0, or +1. (Hm, in fact, that may be part of the problem. Returning anything else is outside the method contract...)

[LWZ]

It's (not that) important to note that the contract of compareTo/compare does NOT specify -1,0,1. Only the sign matters. The simplest way to implement Integer.compare(x,y) is just return x-y. The specification says the sgn (mathematical) function returns -1,0,1.

I suspect it's the transitive property that's failing, because I saw someone with that problem while looking up the error. The other option is antisymmetry. Or:
"Finally, the implementer must ensure that x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z."

Also, I wasn't sure about the cast after what you said, so I tested it:

Code: Select all

//prints 0
public class test{public static void main(String args[]){
System.out.println((int)(-.5));
}}

[Azhrei]

It's (not that) important to note that the contract of compareTo/compare does NOT specify -1,0,1. Only the sign matters. The simplest way to implement Integer.compare(x,y) is just return x-y. The specification says the sgn (mathematical) function returns -1,0,1.

Ah, thanks. I read through the javadoc two quickly.

I suspect it's the transitive property that's failing,

Agreed. Possibly due to precision issues.

Also, I wasn't sure about the cast after what you said, so I tested it:

Wow, you're right:

The Java programming language uses round toward zero when converting a floating value to an integer (§5.1.3)

I never would have thought that to be the case! I know there are differences between C/C++ and Java, but I didn't suspect this was one of them. Due to this and the precision of floating point, it might be that (int)(a-b) does not equal -(int)(b-a) and therein may lie the transitive property error...

Edit: It also just occurred to me that we should probably use an epsilon value in the comparison as well, to help deal with precision issues. I'll think about the best way to handle this and build a new patch. Thanks for the discussion!

[LWZ]

I know there are differences between C/C++ and Java, but I didn't suspect this was one of them. Due to this and the precision of floating point, it might be that (int)(a-b) does not equal -(int)(b-a) and therein may lie the transitive property error...

mingw, at least, also makes it 0. I'm not sure if the C standard specifies a behavior, but this is the rounding mode I'm used to.

From my understanding, that single subtraction is pretty safe (and also not used in the committed code). I personally think that the problem is in the distance calculations. I'll look at that more.

Edit: A threshold might work. I recommend not sorting at all. The code doesn't take advantage of the sorted order, and the idea is to sort points by how far away they are from the origin, which doesn't make too much sense. Since it's a local variable, it should be a safe fix.

This means my work to change to Point (int) was kind of pointless.

[Lee]

My comment was in regard to the image you included on your first post. Looking at that and what you were trying to fix, both were unrelated. On the topic of specifications, versions prior to Java 7 ignored contract violations as the norm, whereas J7 wants stricter enforcement. This implies that one can ignore the violation like in versions 7- and still benefit from the updated algorithm, especially when the application does not benefit from explicit handling of the contract. MT is such an application.

Edit:
If you started on this because of the error you encountered, it was spawned out of the FogUtil class (as it says on the stack trace). In this case, there is benefit in sorting as it involves visible area assessment, and subsequent adding to discovered space, based on a token's perspective.

[LWZ]

I can't find the source for GeometryUtil.getDistance. Halp!

Edit: Disregard, I suck.

Edit:
Can the problem be reproduced reliably? If so, can someone try refactoring this

Code: Select all

public double getDistanceFromOrigin() {
	return GeometryUtil.getDistance(getCenterPoint(), origin);
}

to this?

Code: Select all

private double getDistanceSqFromOrigin() {
	return origin.distanceSq(getCenterPoint());
}

Edit: I remember this being pointed out in a different topic, but since it wasn't changed, I'll point it out again just in case:

Code: Select all

public static double getDistance(Point2D p1, Point2D p2) {
	double a = p2.getX() - p1.getX();
	double b = p2.getY() - p1.getY();
	return Math.abs(Math.sqrt(a+b));
}

Is there any reason why that shouldn't be this?

Code: Select all

public static double getDistance(Point2D p1, Point2D p2) {
	return p1.distance(p2);
}

[Lee]

What's your purpose in fixing this? Is the result of this method you're pointing out returning erroneously and thus breaking whatever you're trying to make in MT? Or are you just bothered by the error per se? I ask because there should be merit to effort, not just making an effort for the sake of it. If it's the latter then all your work will be for nothing if ever Az or the devs write in a blanket fix for the error, which is what I've been trying to explain on my prior posts.

Also, it seems you don't even have a use case since you're asking people to reproduce the error and refactor code to your specifications. Furthermore, since you're closer to the answer than anyone looking at that part of the code right now, why not answer the last question yourself by rooting it out personally? This is especially true since you're evidently someone with programming skills. Azhrei accepts patch submissions and it would be more helpful if you take it out of his hands and complete this work yourself if the end result is important to you. It's what most unofficial devs do here to help, actually.

I'm just saying. Peace.

[LWZ]

The image was taken by someone else. I don't use MapTool, because I don't play anymore, though I was helping the campaign out with changing macros. This is a thing to do, and I'm learning from it.

My efforts to fix the code to use ints has been forestalled because I don't know what I'm playing with. I need, like, a mentor, if I'm to progress on this.

[Lee]

Hmm. You couldn't have picked a more difficult section of the code to tackle. What more, it is something no one here is likely to want touched unless the change would drastically improve performance. It IS one of the defining features of MT that sets it apart from other VTTs, after all. If you don't have anything specific to implement, don't touch VBL at all, because it works fine as it is.

Honestly, without such a performance goal, I don't expect anyone would be motivated much to supply the information you are looking for, because, from what I can tell, you are simply doing this to educate yourself in general. Perhaps when the final build is released, the people involved would have more time for your request.

Without going into too much detail, those 2 area-related classes play a part of the overall vision system and it is how MT keeps track of area "layering" (ie. oceans in islands except for the biggest ocean, which holds all islands). It is necessary to divide larger areas into smaller ones in order to determine relative vision, not to mention it is useless to process areas outside a token's purview, unless one wants to choke MT every time a token moves one step.

[LWZ]

Heh. I tried looking over chartool and the macro execution, and THAT looked so difficult I just gave up. Anyway, the primary goal is to clean up what I can, and I'm justifying my use of time by learning through it.

My question about vbl is because it seems like SOME parts of the code are legacy, while others aren't. AreaFace appears in both it and its parent package, for example, as does AreaMeta. I was really asking, "If I want to change this, do I change the VBL version or the parent version?"

Anyway, I'm giving up on this after tonight and uploading what I have, due to life.

------------------

Here's another mathematical error, but it probably doesn't lead to bugs because it's consistent in the important way (probably). My revisions try to remove the use of this function.

Code: Select all

public static double getAngle(Point2D origin, Point2D target) {
	
	double angle = Math.toDegrees(Math.atan2((origin.getY() - target.getY()),(target.getX() - origin.getX())));
	if (angle < 0) {
		angle += 360;
	}
	
	return angle;
}

This returns the NEGATIVE of the angle. Equivalently, it computes the clockwise angle, rather than the counterclockwise angle.

Testing:

Code: Select all

Point o = new Point(0,0);
Point t = new Point(1,1);

System.out.println(getAngle(o,t)); //should be 45 degrees, but is 315

Edit: I am wrong about the angle. I just learned about Java's user space coordinate system, which has the Y axis going down.

Edit: I am wrong about being wrong about the angle. I am PARTIALLY wrong about the angle. The Java user space coordinate system is clockwise, and the angle computed is still in the opposite direction of the coordinate system. Java's way just swaps up/down and clockwise/counterclockwise, but the definition of angles should remain the same.

[LWZ]

I created a GridPoint class that inherits from java.awt.Point as a Point2D class with integer coordinates, to help me with the refactoring.

I haven't figured out why VisibleAreaSegment.getArea() adds those really long projected points to the list, and thus I can't change them to use integers.

I tried to get rid of GraphicsUtil.getProjectedPoint completely. The only thing stopping me is, again, VisibleAreaSegment.getArea().

The other red marks (vbl.AreaTree, zone.AreaData) are places where the code gets arbitrary paths and makes points out of them, making it impossible to use integer coordinates without a more abstract understanding of what paths can exist.

GridPoint's extra functions (functions that aren't in java.awt.Point) ended up not used (except in getProjectedPoint). I tried to do the computations directly because premature optimization is the best thing ever. The upshot of this is that GridPoint can be completely replaced by Point once getProjectedPoint dies (and one more location, but that one is just a toString for debugging). If the red marks can't be removed, or if you want to test my work, then replace all of the GridPoints with Point2D.Doubles, and change all of the .x and .y to .getX() and .getY().

In GraphicsUtil, I changed the broken and unused createLine function to something that works, but might not be what's wanted. Oh well. I also wrote in comments for the original up to a point. The function should probably just be removed.

AreaFace:
+ Combined the two AreaFace classes from the zone and zone.vbl packages.
+ Reworked to reduce reliance on angle measurements. The classes that use it were also reworked. In particular, "midpoint" and the "double facing" variable aren't needed. Instead, I keep a "facing" point that represents a direction, and a faceTo(Point) function that (like compareTo) returns a positive, negative, or 0 that tells you whether the face is facing toward, away, or neither (is colinear with) relative to the given point.
- Notably, there is a question about facing that hasn't been resolved. See main for testing against the old way. faceTo(Point) can stay, but the meaning of its return is up for debate, so faces(Point) may need to change, and the comments about them, too.
- The code that uses facing (AreaMeta) needs to be tested with this new way. The Geometry.getAngle weirdness is screwing me up. But every time I think I proved that my code is wrong, it still works.
- "boolean faces(Point)" also needs to deal with the case of the line segment being colinear with the origin in question. My opinion is, choose the way that eliminates the most faces, so you deal with less.

AreaMeta: There are two. I worked with them as similarly as I could.
+ Eliminated the circular link list and replaced it with a non-circular ArrayList. Should be a minor speed improvement.
+ Add detection of emptiness. It should never come up, but if your code wants to check for emptiness...
+ Changed the computation for holes: replaced angle-based computation with area-based computation, which should be a speed improvement, since trig is not as fast as a few basic int operations.
- I would've combine the two AreaMetas, but I needed more time to understand them.
- The two AreaMetas have different behaviors when abs(angle) == 90. I don't know why, but I assumed it was an oversight gave them the same behavior (or at least tried to).
- The two AreaMetas also have reversed faces from one another, in computeFaces(). In other words, when one added Face(A,B), the other added Face(B,A). No idea why, but I just realized it may screw up my facing test in getVisibleAreas/getVisibleAreas, and also mean that they DID have the same behavior for abs(angle)==90.

VisibleAreaSegment:
+ Changed the algorithm for getPath, as well as the internal data structure to something less redundant.
- Want to reduce getArea().
- I bet the faceList could be eliminated completely in favor of a list of vertices.

Zip with the zone and vbl package files attached. GraphicsUtil is here: https://dl.dropbox.com/u/2954556/GraphicsUtil.java

[Lee]

Thanks for the effort LWZ, I hope it pays off. To answer a couple of your comments, while the math you mentioned seems erroneous when thought about in the conventional sense, it was borne (from what I can tell) from working with the image assets MT employs, where their initial orientation may give an insight as to why such schemes have been implemented. So, from that standpoint, it's less of a mathematical implementation over a visual one.

Tooling around with the visible area implementation is "dangerous". It is after all, as I mentioned before, a critical visual component that keeps track of what is seen/can be seen on a map. Again, this is relative, which is why it is a collection of areas put together by intersection.

There are a couple of questions that have to be asked about what you're doing. Firstly, have you tested your code thoroughly enough to be sure nothing has been broken? Secondly, what are the improvements accrued, and which of these can be seen by even an MT layman?

If you haven't noticed yet, MT employs 2 coordinate schemes: one that is tied to a grid, and another that is free of it. Both of these employ their own exclusive Point system. These would be the first features I would think of that would be impacted by whatever changes you're making to grid structure and management.

As evidenced by what you're doing, the MT source can use a lot of cleaning up. My advice is to either work on areas of the code that need improvement and that actually get used (you mentioned on your post stuff that weren't so I'm thinking that ROI for effort is low), or you can take your ideas for a good grid implementation outside MapTool, do a standalone for it, and suggest it for MT 1.4 where the official devs are more than willing and happy to field these ideas.

BTW, code patches are submitted on the Testing section of the forums. This area is dedicated to real bugs that cause real runtime failures. Your post in general might be better suited to the Developer Notes section since it posits a change to the tool.