Junction in cable network problem [UNSOLVED] [1.7.10]

[TheEpicTekkit]

Hello everyone.

 

So I have been working on an energy network for my mod. If you have seen my other posts about actually getting it to cascade down the path, I have achieved this, but there are some problems, i.e. the game freezes (doesn't crash, and this is the annoying thing, as I cant diagnose the problem as there is no error report, it just hangs until closed) when it encounters a junction in the path.

 

So what I have done, is make it place a stone block above the cable it is scanning, so that I can visually see what it is doing, and it seems to work fine without a junction. But when it encounters a junction, it hangs.

 

So, when it encounters a junction, what I have made it do is create a new Node (the class that represents the x, y, z coords, and other info about the block) at the currently being scanned coords, and then add it to a PriorityQueue of backtrack locations, also, it saves the currently scanned range to a HashMap with the node as the key so that when it resumes the search from the head of the queue, the scanned range is reset back to whatever it was when it added that backtrack node to the queue. When this happens, it still remembers which cables have already been scanned, so really, from the backtrack point, the only possible direction, is the route it didn't transverse. But instead, it freezes up when this happens.

 

A point that may be helpful is that it scans in the order of ForgeDirection. So it will scan down (side 0) first, then it will scan up (side 1), then north (side 2) etc.

 

This is a simple example of a path it will freeze up on:

C C C C C               3 4 5
    C                   2
    C                   1
    F                   0

(This looks weird in the "modify message" page, I hope it looks okay in the main page... It is a 'T' shape of cables)

"C" represents the cable, and "F" represents the fuse box (this is the block that triggers the scan when placed. It will store all the network data). The numbers represent the weight (or range) that has been scanned.

 

So the moment the fuse box is placed at the end of the cables there, it will place stone blocks above each of the cables that I have shown to have a weight, and the other two don't get scanned, instead, it freezes. It should backtrack to the cable with the weight of 3, as there was more than one possible route for it to take.

 

This is my code (This is quite a long class and method):

        public class Search { //This class is a nested class of "Grid". grid stores all the main data of the network, this class just locates everything in the network if needed

	private int xStart, yStart, zStart, x, y, z, maxRange, currentRange;
	private Grid grid; //The "Grid" this search is a part of
	public boolean isFinished = false;
	public boolean debug, doBacktrack;

	/**A list of available nodes that are networked. This does not include cables, instead machines that can supply power*/
	public List<Node> supplyers = new ArrayList<Node>();
	/**A list of available nodes that are networked. This does not include cables, instead machines that can consume power*/
	public List<Node> consumers = new ArrayList<Node>();
	/**A map of cables.*/
	public List<Node> cableMap = new ArrayList<Node>();
	/**This is a list of locations where there would have been a junction in the cable, and after reaching the max range, or the end of the current route, will backtrack to this location and scan down the un-scanned route*/
	public PriorityQueue<Node> backTrack = new PriorityQueue<Node>();
	/**A list of scanned nodes*/
	public HashSet<Node> scannedNodes = new HashSet<Node>();
	/**This map contains the range that had been scanned from a backtracked point. So, if it backtracks to a point, the currently scanned range will be set to whatever it was when this point was added to the list*/
	public Map<Node, Integer> backTrackRange = new HashMap<Node, Integer>();

	public Search(int x, int y, int z, int range, Grid g) {
		System.out.println(x + " " + y + " " + z);
		this.xStart = x;
		this.yStart = y;
		this.zStart = z;
		this.maxRange = range;
		this.grid = g;
		currentRange = -1;
	}

	public void initNodeSearch() {
		this.x = xStart;
		this.y = yStart;
		this.z = zStart;
		doBacktrack = false;

		currentRange = 0;
		locateNodes(true, x, y, z);
	}
        
                /**
	 * Locate all the nodes connected to the TileEntity calling this method at the parsed coords. This is a recursive
	 * method until it has reached the maximum range. 1 is added to the current range each time the method successfully runs.
	 */
	public void locateNodes(boolean doWork, int x, int y, int z) {

		System.out.println(""); //These are just to make it clear where the method gets recursed, because there is a lot printed in the console.
		System.out.println("");
		System.out.println("Recursing...");
		if (doWork) {

			int directionsScanned = 0;
			boolean[] validDirections = new boolean[ForgeDirection.VALID_DIRECTIONS.length];
			boolean hasValidRoute = false;
			int validCount = 0;

			for (ForgeDirection d : ForgeDirection.VALID_DIRECTIONS) {
				System.out.println(""); //This is just to separate each side scanned with a space.
				System.out.println("Scanning side " + d.ordinal());
				int x1 = d.offsetX + x, y1 = d.offsetY + y, z1 = d.offsetZ + z;
				TileEntity t = world.getTileEntity(x1, y1, z1);
				Node target = new Node(x1, y1, z1, grid);

				System.out.println(x1 + ", " + y1 + ", " + z1 + " Being Scanned");
				++directionsScanned;
				System.out.println(directionsScanned + " scanned");

				//System.out.println("Validating TileEntity on side " + d.ordinal() + " At coordinates X: " + x1 + ", Y: " + y1 + ", Z: " + z1 + ". " + " That node has " + (hasBeenScanned(target) ? "been scanned" : "not been scanned"));
				System.out.println((t == null ? "Null tileentity" : "TileEntity is not null"));
				if (t != null) {
					System.out.println("A tile exists to scan");
					if (isTileValid(t) && !hasBeenScanned(target)) {
						System.out.println("Valid TileEntity");
						validDirections[d.ordinal()] = true;

						//Update the current x, y, z coords being scanned
						x = x1;
						y = y1;
						z = z1;

						if (t instanceof TileEntityFuseBox) { //The controller block of the network. This stores all the data of the network, and triggers this search when placed (and under other circumstances, but not every tick. Too laggy)
							System.out.println("Found fuse box at " + x1 + ", " + y1 + ", " + z1 + ". Current range is " + currentRange + " / " + maxRange + ", and " + (hasValidRoute ? "a valid route exists" : "a valid route does not exist"));
							if (currentRange < maxRange) {
								System.out.println("Recursing from fuse box");
								locateNodes(true, x1, y1, z1);
							}
						} if (t instanceof TileEntityCable || t instanceof IEnergyConductor) {
							System.out.println("Found cable at " + x1 + ", " + y1 + ", " + z1 + ". Current range is " + currentRange + " / " + maxRange + ", and " + (hasValidRoute ? "a valid route exists" : "a valid route does not exist"));
							target.setValidation(getValidation(t));
							this.cableMap.add(target);
							markScanned(target, true);
							currentRange++; //Only add to the range if this is a cable, else it is a machine, and should not affect the current range

							if (currentRange < maxRange) {
								world.setBlock(x1, y1 + 1, z1, Blocks.stone);
								System.out.println("Recursing from cable");
								locateNodes(true, x1, y1, z1);
							}
						} if (t instanceof IEnergySupplyer) {
							System.out.println("Found supplyer at " + x1 + ", " + y1 + ", " + z1 + ". Current range is " + currentRange + " / " + maxRange + ", and " + (hasValidRoute ? "a valid route exists" : "a valid route does not exist"));
							target.setValidation(getValidation(t));
							this.supplyers.add(target);
							markScanned(target, true);

							if (currentRange < maxRange) {
								System.out.println("Recursing from supplyer");
								world.setBlock(x1, y1 + 1, z1, Blocks.gold_block);
								locateNodes(true, x1, y1, z1);
							}
						} if (t instanceof IEnergyConsumer) {
							System.out.println("Found consumer at " + x1 + ", " + y1 + ", " + z1 + ". Current range is " + currentRange + " / " + maxRange + ", and " + (hasValidRoute ? "a valid route exists" : "a valid route does not exist"));
							target.setValidation(getValidation(t));
							this.consumers.add(target);
							markScanned(target, true);

							if (currentRange < maxRange) {
								System.out.println("Recursing from consumer");
								world.setBlock(x1, y1 + 1, z1, Blocks.coal_block);
								locateNodes(true, x1, y1, z1);
							}
						}
					}
				}

				if (directionsScanned >= 6) {
					for (boolean b : validDirections) { //Count the number of true values in the array.
						validCount += (b ? 1 : 0);
					}

					if (validCount > 0) { //There is a possible routes (it is not a dead end)
						hasValidRoute = true;
						doBacktrack = false;

						if (validCount > 1) { //If there is more than one possible route
							Node n = new Node(x, y, z, grid);
							System.out.println("Adding backtrack point at X: " + x + ", Y: " + y + ", Z: " + z + ", with a range of " + currentRange);
							this.backTrack.add(n); //Add this location to the list to return to later
							System.out.println("Success. Saving range");
							this.backTrackRange.put(n, currentRange);
							System.out.println("Range saved");
						}
					} else {
						System.out.println("No valid routes, attempting backtrack");
						doBacktrack = !backTrack.isEmpty();
					}

					if (currentRange >= maxRange) {
						System.out.println("Reached maximum range... Attempting backtrack");
						doBacktrack = !backTrack.isEmpty();
					}

					if (doBacktrack) {
						System.out.println("Attempting backtrack - the queue is " + (backTrack.isEmpty() ? "empty" : "not empty"));
						if (!backTrack.isEmpty()) {
							System.out.println("Has available backtrack point");
							Node n = backTrack.poll(); //Get the last backtrack point from the queue (I am right in thinking that poll( ) gets the value, then removes it, right?)

							System.out.println("Retreiving range from map");
							if (backTrackRange.get(n) >= 0) { //Get the range the scan was on when this backtrack point was added to the list
								System.out.println("Backtrack range is positive, backtracking");
								currentRange = backTrackRange.get(n);
								System.out.println("Backtracking to possible junction at X: " + n.x() + ", Y: " + n.y() + ", Z: " + n.z() + " with backtrack range of " + backTrackRange.get(n));
								locateNodes(true, n.x(), n.y(), n.z()); //Recurse this method from the coordinated of the last backtrack point in the queue.
							}
						}
					} else if (!doBacktrack && !hasValidRoute && !isFinished && backTrack.isEmpty()) {
						System.out.println("Finished 1"); //Labelled "Finished" with 1 or 2 so that I could tell which case it was terminating on.
						isFinished = true;
						return;
					}
				}
			}	
		} else {
			System.out.println("Finished 2");
			return;
		}
	}

 

So as you can see, there are a lot of System.out.println()s in there, I dod this to help me track where the problem is, but I cant seem to figure it out.

 

This is the console output for the path example I showed above if it helps:

Recursing...

Scanning side 0
221, 70, 247 Being Scanned
1 scanned
Null tileentity

Scanning side 1
221, 72, 247 Being Scanned
2 scanned
Null tileentity

Scanning side 2
221, 71, 246 Being Scanned
3 scanned
TileEntity is not null
A tile exists to scan
Valid TileEntity
Found cable at 221, 71, 246. Current range is 0 / 64, and a valid route does not exist
Recursing from cable

Recursing...

Scanning side 0
221, 70, 246 Being Scanned
1 scanned
Null tileentity

Scanning side 1
221, 72, 246 Being Scanned
2 scanned
Null tileentity

Scanning side 2
221, 71, 245 Being Scanned
3 scanned
TileEntity is not null
A tile exists to scan
Valid TileEntity
Found cable at 221, 71, 245. Current range is 1 / 64, and a valid route does not exist
Recursing from cable

Recursing...

Scanning side 0
221, 70, 245 Being Scanned
1 scanned
Null tileentity

Scanning side 1
221, 72, 245 Being Scanned
2 scanned
Null tileentity

Scanning side 2
221, 71, 244 Being Scanned
3 scanned
TileEntity is not null
A tile exists to scan
Valid TileEntity
Found cable at 221, 71, 244. Current range is 2 / 64, and a valid route does not exist
Recursing from cable

Recursing...

Scanning side 0
221, 70, 244 Being Scanned
1 scanned
Null tileentity

Scanning side 1
221, 72, 244 Being Scanned
2 scanned
Null tileentity

Scanning side 2
221, 71, 243 Being Scanned
3 scanned
Null tileentity

Scanning side 3
221, 71, 245 Being Scanned
4 scanned
TileEntity is not null
A tile exists to scan

Scanning side 4
220, 71, 244 Being Scanned
5 scanned
TileEntity is not null
A tile exists to scan
Valid TileEntity
Found cable at 220, 71, 244. Current range is 3 / 64, and a valid route does not exist
Recursing from cable

Recursing...

Scanning side 0
220, 70, 244 Being Scanned
1 scanned
Null tileentity

Scanning side 1
220, 72, 244 Being Scanned
2 scanned
Null tileentity

Scanning side 2
220, 71, 243 Being Scanned
3 scanned
Null tileentity

Scanning side 3
220, 71, 245 Being Scanned
4 scanned
Null tileentity

Scanning side 4
219, 71, 244 Being Scanned
5 scanned
TileEntity is not null
A tile exists to scan
Valid TileEntity
Found cable at 219, 71, 244. Current range is 4 / 64, and a valid route does not exist
Recursing from cable

Recursing...

Scanning side 0
219, 70, 244 Being Scanned
1 scanned
Null tileentity

Scanning side 1
219, 72, 244 Being Scanned
2 scanned
Null tileentity

Scanning side 2
219, 71, 243 Being Scanned
3 scanned
Null tileentity

Scanning side 3
219, 71, 245 Being Scanned
4 scanned
Null tileentity

Scanning side 4
218, 71, 244 Being Scanned
5 scanned
Null tileentity

Scanning side 5
220, 71, 244 Being Scanned
6 scanned
TileEntity is not null
A tile exists to scan
No valid routes, attempting backtrack
Finished 1

Scanning side 5
220, 71, 244 Being Scanned
6 scanned
TileEntity is not null
A tile exists to scan

Scanning side 5
221, 71, 244 Being Scanned
6 scanned
TileEntity is not null
A tile exists to scan

Scanning side 3
221, 71, 245 Being Scanned
4 scanned
TileEntity is not null
A tile exists to scan

Scanning side 4
220, 71, 244 Being Scanned
5 scanned
TileEntity is not null
A tile exists to scan

Scanning side 5
222, 71, 244 Being Scanned
6 scanned
TileEntity is not null
A tile exists to scan
Valid TileEntity
Found cable at 222, 71, 244. Current range is 5 / 64, and a valid route does not exist
Recursing from cable

Recursing...

Scanning side 0
222, 70, 244 Being Scanned
1 scanned
Null tileentity

Scanning side 1
222, 72, 244 Being Scanned
2 scanned
Null tileentity

Scanning side 2
222, 71, 243 Being Scanned
3 scanned
Null tileentity

Scanning side 3
222, 71, 245 Being Scanned
4 scanned
Null tileentity

Scanning side 4
221, 71, 244 Being Scanned
5 scanned
TileEntity is not null
A tile exists to scan

Scanning side 5
223, 71, 244 Being Scanned
6 scanned
TileEntity is not null
A tile exists to scan
Valid TileEntity
Found cable at 223, 71, 244. Current range is 6 / 64, and a valid route does not exist
Recursing from cable

Recursing...

Scanning side 0
223, 70, 244 Being Scanned
1 scanned
Null tileentity

Scanning side 1
223, 72, 244 Being Scanned
2 scanned
Null tileentity

Scanning side 2
223, 71, 243 Being Scanned
3 scanned
Null tileentity

Scanning side 3
223, 71, 245 Being Scanned
4 scanned
Null tileentity

Scanning side 4
222, 71, 244 Being Scanned
5 scanned
TileEntity is not null
A tile exists to scan

Scanning side 5
224, 71, 244 Being Scanned
6 scanned
Null tileentity
No valid routes, attempting backtrack
Adding backtrack point at X: 222, Y: 71, Z: 244, with a range of 7
Success. Saving range
Range saved

Scanning side 3
221, 71, 246 Being Scanned
4 scanned
TileEntity is not null
A tile exists to scan

Scanning side 4
220, 71, 245 Being Scanned
5 scanned
Null tileentity

Scanning side 5
222, 71, 245 Being Scanned
6 scanned
Null tileentity

Scanning side 3
221, 71, 247 Being Scanned
4 scanned
TileEntity is not null
A tile exists to scan

Scanning side 4
220, 71, 246 Being Scanned
5 scanned
Null tileentity

Scanning side 5
222, 71, 246 Being Scanned
6 scanned
Null tileentity

And that is the point that it crashes. From here, there are just "Can't keep up! Did the system time change, or is the server overloaded?" posted in the console every minute or so.

 

Any help diagnosing why this is happening, and even how I could fix this would be appreciated. I mainly just want to know why this is happening for now, I could probably fix it if I know that.

 

Thanks.

[TheEpicTekkit]

Bump*

 

Really need help, I have been trying to figure this out for the last 7 to 8 hours now... And annoyingly the debug perspective in eclipse isn't behaving properly.

[hugo_the_dwarf]

I figured since you said a normal "one way" cable route worked fine (at least no freeze ups) That it would be your back trace code and or your search code. I find it a bit odd, you want to seach all 6 forge directions yet your output log shows the first leap going 0, 1, 2 found it, starting from cable,

 

then 0, 1 ,2 recursing from cable. once again 0, 1, 2 recursing from cable. But then, from the looks of it you hit your junction 0, 1, 2, 3 Found Something, 4 Got something again recursing from cable.

 

now you see the problem I have (unless you cut the log short) is that you have the foreach loop for all forge directions, yet I only see output for the 1st or 2nd found tileEntity when in reality I should see: 0,1,2,3,4,5 (all six)

 

And now for the next question, why a back track? you run a recursive call on each cable anyways (understandable) so why the need to make a back trace, just trace all the way until there are no more cables. I figure you get a hang up because that backtrace junction literately gets stuck at that "T" and not only that checks down the 1st line forever, example would be:

 

Cable scan finds junction, saves it (this is that "T") continue down the right path (I am guessing this is direction 4) reach the end, found nothing important back trace. Return to Junction "T" rescan down path 4, and look at path 3 (left?) well the 1st point down that junction is gonna stop and scan down path 4 (right, which is heading back not down the path) which scans the "T" junction and then goes down path 4(right) again, all the while creating another recursive path until you have game freeze from so many recursive loops generating until the end of time.

 

So what you need to do, is check if that cable has been scanned already in that time frame, or have the cable focus one a direction "locateNodes(true, x1, x2, x3, ForgeDirection)" this way it should scan that way 1st before going 0,1,2,3,4,5.

 

so Look over your scanning code, and see why it's not stopping and already scanned cables and checking for new ones.

[TheEpicTekkit]

Okay, I have definitely not cut anything short from the console output (other than everything irrelevant before I placed the fusebox like logging in etc) And I did notice that it was outputting some strange things, eg, the fact that it scanned 3, 4, 5 (and then without recursing) scanned 3, 4, 5 again. Currently, as soon as it finds an available / valid node to move to, it will go to it, and forget about whatever remaining directions there are left to scan. To be honest, come to think of it, this probably shouldn't be the case.

 

So what you are saying, is that I should have it scan al six sides before moving onto the next cable? or that it should have a ForgeDirection parameter in the method to use when recursing?

 

I have a backtrack because, it doesn't split off in both (or more) directions at a junction. I don't know how I would achieve this, and so what it does, is go down the first valid direction it can, and as a result, only travels down one path, any junction (before I set up the backtrack code) would be left completely alone.

 

Also, the cables (Node) gets marked as scanned, so when it returns to the head of the backTrack queue, logically, it should take the unscanned path, and not continue back down the already scanned path. Also, without marking it as scanned, the method would scan around the first cable, find an adjacent cable, scan around that, find the first cable, scan around it, find the second cable, scan around it, find the first cable etc, it would just jump back and forth between those two until it has recursed 64 times (the range limit). This was what was occurring before I figured out how to mark the node as scanned (I discovered that in the Node class I had to override equals(Object o) {...} to hold some custom info, and compare the coords of the nodes, hashCode() {...} because that is apparently good practice to override when overriding equals, and also I had to implement Comparable<T> to make the list / set / queue work properly with the Node)

 

You said to find out why it isn't stopping at already scanned cables, it is though. That is kind of the strange thing.

[gcewing]

You seem to be using a mixture of two different algorithms, a recursive one and a non-recursive one. If you're keeping a queue of backtracking locations, you should *not* also be making recursive calls.

 

It's usually better to do this kind of thing non-recursively, because then there's no danger of running out of stack space for complicated networks. The skeleton of a non-recursive graph traversal algorithm goes something like this:

 

  set visited_notes to an an empty set

  set nodes_to_visit to an empty queue

  add initial_node to nodes_to_visit

  while nodes_to_visit is not empty:

      pop current_node from nodes_to_visit

      add current_node to visited_nodes

      process current_node

      for each neighbour_node in nodes connected to current_node:

        if neighour_node not in visited_nodes:

            add neighour_node to nodes_to_visit

 

Another advantage of this algorithm is that no special cases are needed for junctions vs. non-junctions -- every node is treated the same, however many connections there are from it.

 

My advices is this:

 

1) Throw away your whole existing locateNodes method. It's FAR too big and complicated as it is, and you'll only drive yourself insane trying to debug it.

 

2) Replace it with something that just implements the bare bones of the traversal algorithm. Essentially it will be a line-by-line translation of the above pseudocode into Java. Split off all the sub-tasks such as "process node" and "find neighbours" into separate methods, where they won't obscure the main algorithm.

 

If you do that, you should end up with something manageable that you can debug.

 

You might also like to do some research into algorithms for traversing graphs -- it's a well-studied subject.

[TheEpicTekkit]

I have done so much research into graph traversal algorithms before attempting this. Mainly DFS, BFS, A-Star, and Diejkstra's algorithm (probably not spelled right) The problem though, is they all have to be parsed two nodes, a from node, and a to node, and they will simply find the shortest route. Now what I need it to do, is locate all the nodes in the first place, and so, from the knowledge of the algorithms I have researched, I have sort of written my own to do so. That is why it is so messy, because it has been trial and error to get it to a working (well, semi working) state.

 

So, you are saying that I should scrap my current method, and rewrite it so that it doesn't recurse?

 

What might be best, and this idea came to me from what Hugo said and would probably involve rewriting the majority of the method anyway, is maybe I could have it split off at a junction, so it will traverse both routes simultaneously, but how would I achieve this?