Trigger a search down a line of blocks (cables) [UNSOLVED] [1.7.10]

[TheEpicTekkit]

Hello everyone.

 

So, I am working on a cable, and I have all but finding power emitters working. So what I need to do, is if a machine is requesting power, it will search for a cable on any of its six sides, if it finds one, one of three things (I am not sure which would be best) would happen.

One, the only thing the block does is trigger a search on the cable, and from there the cable scans down any other cables connected, remembering the location of the requesting block, and passing it to each cable, then if the cable locates a power emitter, will send its location back to the requesting block, and then the requesting block draws power from the emitter.

Two, the cables act as a guide for the requesting block, and a graphical connection for the player. What I mean by guide is the requesting block does all the searching, and the cables are what it follows. So first it will scan for cables immediately adjacent to it, then if it finds one, will search for cables immediately adjacent to that cable, and if it finds a cable immediately adjacent to that one, it will scan for cables around it, etc, until it finds an energy emitter. If the requesting machine finds a cable with more than one cable attached to it, it will scan around all of them (same for if it finds more that one cable directly adjacent to it) and will choose the energy emitter that it finds first.

Three, there is no scanning being done, each cable has an internal buffer of power, and it just passes that power onto the next cable. (I really dont want to do this one, but if it comes to it, I will. This method doesn't seem very flexible with what I can do with the energy)

 

Currently I have been working on the first option, but it is proving more difficult than I expected. Either, the cable doesnt actually scan down the line, and can only detect blocks directly attached to the cable, or I get a stackOverflowError because the cable searches, finds a cable adjacent, triggers a method in the tileentity of the found cable that then restarts the method that found that cable in the first place, thus getting stuck in a loop, and crashing.

 

So, my question is which one of these methods would be the best choice? and how would I go about doing the best method?

 

Thanks for the help.

[hugo_the_dwarf]

I've been trying to post a theory or an idea on how to do a weighted cascade to compliment choice no.1 but my logic just contradicts itself. I know Jabelar posted in your other thread about the idea of the cables updating  themselves using meta data. 0-15(16 total) I think your best bet is to look at how redstone works and engineer that functionality to your cables, emitters and requesters

[TheEpicTekkit]

The thing is though; redstone can only travel 15 blocks, I want my energy to be able to travel about 60 blocks. I do want a limit for two reasons; one, to reduce lag, not that there will be much, but it'll help. Two, I want this to be the maximum, other cables will have a lesser range. The problem with this though, I cant have more than 16 metadata sub blocks.

 

The cables updating themselves is what I have already been trying, but without success.

[hugo_the_dwarf]

Well my idea was to have a ArrayList<ofThisThing>

public class ofThisThing
{
public int x, y, z, distance;
public ofThisThing(int x, int y, int z, int distance)
{
this.x = x;
this.y = y;
this.z = z;
this.distance = distance;
}
}

 

will probably be a temp array (so put it in the scope of a method) you could also make a class called "Route" and it stores a path of cable coords to an emitter but more on that later.

 

you will also need a helper method to calculate distance easy probably something like private int getTotalDistance(cableX,cableY,cableZ,requesterX,requesterY,requesterZ)

{

return ((cableX - requesterX)+(cableY - requesterY)+(cableZ - requesterZ));

}

 

now this is where I get stumped, because you will need a recursive method that calls itself for each cable found, but also references the list of "already found and weighed cables" the requester will send out a "search" command to all attached cables, and these cables will send out "search" commands to all attached cables (but also look for emitters) I have no idea what damage something like this can cause. But you shouldn't have the cascade splash back it should always flow out to cables not already found. If that makes sense?

[TheGreyGhost]

Hi

 

I'd suggest you have basically two reasonable choices

1) Process your nodes and cables into a Graph structure, and update it every time a cable or node is added or deleted.  Graphs are a well-studied area in maths and programming and there are many algorithms which will give you the behaviour you want.

For some intro information about graphs see here.  Warning - it is quite complex.  http://introcs.cs.princeton.edu/java/45graph/

2) Your method #3.  Either - make the distance it can travel infinite (so you don't need to worry about the limited metadata), or use tricks to extend the metadata range.

eg each cable has an internal "buffer" which tells how far the nearest emitter is, i.e the block stores the number of "steps" to the nearest emitter- the first cable next to the emitter stores 1, the one adjacent to that stores 2, etc.  Every few ticks, each cable checks the metadata of the adjacent cables and sets itself to the lowest, plus one.

If you want to have a "maximum travel" of (say) 60 blocks, you can use multiple block IDs for your cables (eg 4 block IDs * 16 metadata -> 64 levels)

 

I think both of them would work provided that you don't have a ridiculous number of cables.

 

-TGG

[TheEpicTekkit]

Okay, I think that the most flexible option would to make a cable scan the six blocks around it, and if one is a cable, trigger a search from that cable, and in my logic, that will go down the path of cables, but also, there are some problems.

 

First, if a cable (cable 1) scans all six sides around it, and finds another cable (cable 2) and triggers a search from that cable, cable 2 would find cable 1 again, and then cable 1 would find cable 2, and they would be stuck in a loop of finding each other, and undoubtedly this would cause a lot of lag. So I would need a way to mark a cable as scanned.

 

Secondly, if the cables find an energy emitter that can supply the machine, how will they send the location of the emitter to the machine, because the way I want to do it, is the machine just has the coordinates of the emitter, and pretty much teleports the power over.

 

Thirdly, how would I make it detect if a block has been removed, or added to the network? because if the cable finds an emitter, and the machine knows the location of it, and is drawing power from it, if the player removes it during this process, it would crash the game with a NullPointerException, or a ClassCastException because the machine is doing something to a block that doesn't exist.

 

Bye the way, by emitter, I mean a machine that can output power, not just generators that produce power.

[hugo_the_dwarf]

it would crash the game with a NullPointerException, or a ClassCastException because the machine is doing something to a block that doesn't exist.

 

DrawPower()

{

TileEntity te = getWorldObj.getTileEntity(x,y,z);

if (te instanceof MyEmitter)

{

//Do draw power stuff

}

else

{

system.out.println("Oh snap, that's not a emitter!");

ArrayList.remove(where this was stored);

}

}

 

First, if a cable (cable 1) scans all six sides around it, and finds another cable (cable 2) and triggers a search from that cable, cable 2 would find cable 1 again, and then cable 1 would find cable 2, and they would be stuck in a loop of finding each other, and undoubtedly this would cause a lot of lag. So I would need a way to mark a cable as scanned.

I mentioned about making a tempArray that the cables can reference, so Cable1 finds Cable2. Cable1 adds itself to the list (personally the machine/requester should do this) and adds Cable2 to the list. Cable2 then finds Cable1 but before saying "search command" it checks the arrayList to see if Cable1 is already in there (which is should find) it will then say "ok no need, but am I in the list?" check list to see if it is in there, add self if not (likewise personally if it started at the requester the cables won't need to check or add themselves, just the new found cables) then look for Cable3.

 

But I had mentioned a list of "Routes" these would be saved to each emitter (Route 1 and Emitter 1) so when the machine needs to draw power it will choose route 1, (which goes down each cable making sure it is there). Also remember I mentioned about a class that holds the x,y,z and distance variables? each point of distance can be used as a weight and your "cable range"

 

TGG has a good points there too, altho I don't understand nor used those methods.

 

[TheEpicTekkit]

Okay, so you're saying that I shouldn't be making the cables do the work, I should be making the machine requesting do all the work?

 

Also, I am looking at buildcrafts source, and I am looking for the way they handle their power net. Any help on locating this method? (Currently looking at: this)

 

Also, another interesting thing I found on github is this from steves factory manager. I am looking at the updateInventories method.

[TheEpicTekkit]

also, this is my location class:

package generator.net.theepictekkit.generator.common.energy;

import net.minecraft.block.Block;
import net.minecraft.tileentity.TileEntity;
import net.minecraft.world.World;

public class NodeLocation {

public static int instances = 0;

public int x, y, z, range;
public Block block;
public TileEntity tile;
public World world;

public NodeLocation(int x, int y, int z, Block block) {
	this.x = x;
	this.y = y;
	this.z = z;
	this.block = block;
	this.instances = this.instances + 1;
}

public NodeLocation(int x, int y, int z, TileEntity tile) {
	this.x = x;
	this.y = y;
	this.z = z;
	this.tile = tile;
	this.instances = this.instances + 1;
}

public NodeLocation(int x, int y, int z, int range) {
	this.x = x;
	this.y = y;
	this.z = z;
	this.range = range;
	this.instances = this.instances + 1;
}

public World getWorld() {
	return this.world;
}

	public void setWorld(World world) {
	this.world = world;
}

public boolean hasWorld() {
	return this.world != null;
}

public int getX() {
	return this.x;
}

public int getY() {
	return this.y;
}

public int getZ() {
	return this.z;
}

public int getRange() {
	return this.range;
}

public TileEntity getTile() {
	return this.tile != null ? this.tile : (this.hasWorld() ? this.getWorld().getTileEntity(x, y, z) : null);
}

public Block getBlock() {
	return this.block != null ? this.block : (this.hasWorld() ? this.getWorld().getBlock(x, y, z) : null);
}

@Override
public String toString() {
	if (block != null && tile == null) {
		return "X:" + x + "Y:" + y + "Z:" + z + "_" + block.getUnlocalizedName() + "_" + this.instances;
	} if (tile != null && block == null) {
		return "X:" + x + "Y:" + y + "Z:" + z + "_" + tile.getWorldObj().getBlock(x, y, z).getUnlocalizedName() + "_" + this.instances;
	}
	return "X: " + x + "Y: " + y + "Z: " + z + "_null_" + this.instances;
}
}

[hugo_the_dwarf]

Seems like you have quite a complicated location class (not that it's bad, or hard to understand.) I personally try not to save a tileEntity (as I have no idea what happens if it changes, does it update? Is it only a reference?) I just save its "last known coordinates" and "get" it when the time comes, that way I will always know it is fresh (because I got the newest update of it) and can make sure it is still there.

 

But how I would set it up would be:

 

public class BlockLocation
{
public int x, y, z, distance;
public BlockLocation(int x, int y, int z, int distance)
{
this.x = x;
this.y = y;
this.z = z;
this.distance = distance;
}
}

public class PowerRoute
{
//X, Y, and Z of tileEntity
public int x, y, z;
private blockLocation[] route;
public PowerRoute(int x, int y, int z, BlockLocation[] route)
{
this.x = x;
this.y = y;
this.z = z;
this.route= route;
}
}

 

I would then have class variables in the tileEntity called:

private ArrayList<PowerRoute> powerSources = new ArrayList<PowerRoute>();

private ArrayList<BlockLocation> cableMap = new ArrayList<BlockLocation>();

 

A few methods called:

private int distanceFromMe(int x, int y, int z)
{
return ((x - this.xCoord)+(y - this.yCoord)+(z - this.zCoord));
}

 

private boolean isInCableMap(int x, int y, int z)
{
BlockLocation cable = new BlockLocation(x,y,z,distanceFromMe(x,y,z));
if (cableMap.isEmpty)//If empty just add it
{
cableMap.add(cable);
return false;
}
else //since the map has something..
{
//Check through the map comparing each cable
for (int l = 0;l < locations.size();l++)
{
if (cableMap.get(l).equals(cable))
{
return true;//Already had it return true;
}				
}
//Couldn't find it so add it
cableMap.add(cable);
return false;	
}
}

 

Just for the initial setup, these two methods should help me perform the trickier logic of "flowing down the cables" now I am going to only write out the logic of how i'd do it, because I know it's gonna be broken as heck and I know i'm gonna have some fun making this for my own mod when i get around to "Powered" things. And this is gonna be long winded so forgive me.

 

My tileEntity will have a few methods, and these ones will be slightly big but will ensure cpu hungry methods don't need to be called often only when needed.

 

cleanCableMap()

{

/* This method will grab the instance of it's world "World w = this.getWorldObj();"

with this World "w" it will go through the cableMap and make sure that all cables still exsist, look at isInCableMap but instead of returning it tries to get the block

such as 

BlockLocation cl = cableMap.get(l);

Block cable = w.getBlock(cl.x,cl.y,cl.z);

if (cable instanceof BlockCable)nothing this is fine

else cableMap.remove(l);//It's not a cable or it's null/air remove it from the list.

*/

}

the cleaning will probably run every 5 or 6 seconds (100 to 120 ticks maybe more) just to try and give the server a break here and there (forseen issue, what if there are a lot of these tileEntities I mean A lot, a ton of lists being cleaned at once.)

 

 

Ok i'm going to have to make another post this is too long.

[hugo_the_dwarf]

Part2:

 

Going to spoiler this whole post: "Also not to self, this is harder then I thought"

 

 

ok now that I have my map cleaning method it's time to try to pan out the weighted cascade, now since this is probably going to be the most cpu hungry method it should only be called very rarely, so it's best for it to extract as much information as it can in one go and I have a few ideas on how to make it work less and accomplish more. Ok so this method starts first my collecting all nearby power sources, now you said the max range of the best cable is 60, so that means you have plans for "lesser" cable types. I have no idea what your cables have but I suggest this setup if you haven't already:

BlockCable extends Block (or whichever style you are using to render it) //also add a method to return a "range" variable, make the variable too

BlockGoodCable extends BlockCable //set the range (hope you made a setter method for it too, getters need setters) which can be 60, 40, 20, whatever. since this is "good" it's 60

 

so we know the machine will look at all 6 sides, so we do that first to test the waters so to speak. Lets start with one side at a time how about, north.

ArrayList<TileEntityPowerMaker> emitters = new ArrayList<TileEntityPowerMaker>(); 

Block cable = this.getWorldObj.getBlock(this.xCoord,this.yCoord,this.zCoord - 1);

int range = -1;

if (cable instanceof BlockCable)

{

range = ((BlockCable)cable).getRange();

isInCableMap(this.xCoord,this.yCoord,this.zCoord - 1);//this is nice no need to do any checks because this adds or ignores cables in here already

}

if (range != -1)

{

// in here will be a triple for loop nest all starting at -range + 1 and ending at range - 1

//looking for tileEntities and comparing them to a power emitter if it is and instance of it, add it to the list

if (!emitters.isEmpty())

{

//Now if some emitters are found we can begin to search the cables

/* I would try a for loop with a set amount of runs, with a clause that will also break out if no more cables can be found.

and somewhere in here I might have a variable that holds the current "distance" run, reason for this is the cableMap is going to get read over and over until this is done or no more cables are found so will need a boolean "cableFound" with a if statement that will "break;" if it is false.

so the for loop will look something like this

for()

{

for(i; i < cableMap.size(); i++)

{

BlockLocation cableSpot = cableMap.get(i);

if (cableSpot .distance == targetDistance)

{

//Look at all the blocks around these cables, using isInCableMap();

//So if distance is 1, it will find the first cable added, and with that cable check the 6 sides for other cables adding them.

//for loop ends, targetDistance++; next time "tada" those new cables are now searching, and they won't make duplicates because the method for adding them handles that

//they will go on until

//also in the first sucess do a "if (!cableFound) cableFound = true;

//and if you are wondering why I'm going this route, it's so that all cables that are connected are added into the cableMap to be used as a "traffic path"

}

}

}

if (!cableFound)break;

else

{

targetDistance++;

cableFound = false;//reset for the next loop

}

 

*/ Now that a cable map is built (also I forgot to mention that cables will be found with a world instance and .getBlock and checked with instanceof cable, and if that passes check to make sure that cables range cable.getRange() is equal to the current range (unless all cables can connect if so, well idk how you will handle range differences) if the ranges don't match it's not a good cable to have and is ignored (not added)

}

}

 

Ugh such a long process, hopefully this makes sense or helps you.

//Ok lets say all connected cables with a range of 60 (you use only the best cables) we now have a complete map of it, with distances. these are our weights and how do we make a route (remember I made a class for this). Well we work backwards of course from the first power emitter we have on file (emitters) we get the distance that is it from the requester

int myDist = distanceFromMe(emitter.xCoord,etc..);

 

Now this is where the search function will get tricky, because the weights are to help find the "fastest" route however some people might make some strange connection with the cables (like up over the emitter, down a wall, and to the emitters far side (side farthest from the requestor) so the connected cables in fact are a heavier weight. So when looking at the map, the best way is to find a cable that has a distance < myDist. better make the check of distance = myDist - 1 so it's not checking all good cables, just ones that should be around it (but the problem with this is, how does it know that the further is the only one connected) and this is where my brain shuts down.

 

Probably some way of checking for cables all around it, and going from there, but if that is the case. Why save a map of the cables at all? TGG is right or whoever mentioned path finding is just a headache. I'm off the night, I don't doubt this will be ripped to shreds by the time I get back lol.

 

 

 

[TheEpicTekkit]

Wow.... Thanks for this. You really spend a lot of time trying to help me get this working. I really appreciate that.

[hugo_the_dwarf]

Now been thinking about this, can only post a little have to run off to work. But I don't think the distance needs to be saved because like the issue of "what if there are no straight lines, but some needlessly complex cable route, with dead ends"

 

^

|  =======

|  #          #

|  #          #

|  #          #

Y  === E  ====R

[]X----------------->

With the way I was thinking "E" is emitter and "R" is requester and with the cable weighting system that I "thought" of would probably fail pretty hard (unless you can work off of it and get something working) because the weights would be:

^

|  =====9 8

|  15          7

|  16          6

|  17          5

Y  ==20 E  4321R

[]X----------------->

 

Now that is only a side view of X and Y (staring down the Z axis) the player could also have some dead end branches at certain places. So either the cables need to save their "weights" of distance of an variable that increments (and not a calculation of distance, but a count of hops) that might work better because then dead-end cables that flowed out from the initial path would be weighted higher then the true path.

 

Because the best way would be for the emitter to create a route or the requester to start from the emitter and work back to the requester making a path (saving it as an array) as it goes to save in the arrayList of PowerRoutes that way when it needs to draw power from that emitter, it can check to make sure all the cables are there (if one comes up as null or not the right cable, delete that list and/or try to make a new route)

[TheEpicTekkit]

What if I were to use an A-Star path finding algorithm? Something that actually has tutorials. Currently, this energy grid system has no tutorials. So with A-Star, I could restrict it to the cables. Think this will work?

[TheEpicTekkit]

^

|  =======

|  #          #

|  #          #

|  #          #

Y  === E  ====R

[]X----------------->

^

|  =====9 8

|  15          7

|  16          6

|  17          5

Y  ==20 E  4321R

[]X----------------->

 

I would have thought that A-Star wouldn't have a problem with this.

 

ccccccccc

c          c

c          ccccccc

c                  c

R              Ecc

A path like this for example, 'c' being a cable, 'R' being a requesting machine, and 'E' being an emitter, A-Star wouldn't have a problem with, or really, shouldn't have a problem with. I could specify that all the blank spaces in this example are places that the pathfinder cant scan, so in all the 2d examples of A-Star, the blank spaces are the walls. So that means that the cables are pretty much the only path A-Star is allowed to scan. Does this make sense?

[TheEpicTekkit]

I have found a free pathfinding library, and it seems to be designed for 3D, which is just what I need. I haven't looked at this in detail, only a brief look.

[hugo_the_dwarf]

looks like A* would work nicely however how many loops (or recursive calls) would have to run just for each route? now of course with the weights it would for sure help it decide the fastest route, so combining both would make it work to the best effect. I wouldn't mind if you shared the finished code with me (of course when I get around to using it, or improving it I would of course share those changes with you )

 

but it seems you have everything you need now

[TheEpicTekkit]

Sure. I would show you my power grid code when I have got it working. My main challenge now though is integrating this to work with the mc world. I have done a bit of research on A-Star, and when looking for a free library, I came across other people looking for a library too, and one thing I read is that pathfinding libraries are rare because they really have to be built around the environment you are using it in. So I was lucky to find the one I did, and I was even more lucky as it is built to work with 2D environments and 3D environments, and most pathfinding algorithms I have found are designed for 2D only.

[TheEpicTekkit]

Also....

 

however how many loops (or recursive calls) would have to run just for each route?

 

By "each route" do you mean a junction in the cable? or separate cable networks on different sides of the block?

 

Well, I guess, either way, it will use whatever emitter it finds first. So if there is a junction, it will split at the junction, and go down each route at the same time, and use whatever it finds first. and the same with the separate network on different sides of the block.

[hugo_the_dwarf]

Oh by route I mean "the fastest or first line of cables that connect the emitter to the requester" once it has a route it just saves it to the list and moves to the next emitter to make a "route" until it finds all routes for all emitters. There probably should be a check for each cable to make sure it was included in the map (if even use the map) because if the requester wasn't connected to that cable in the first place, why bother trying to find a route?

 

And then another issue I thought of, is since all these are saved, and not checked every time (in the premise of hoping that saves on cpu and lag reduction, at least that is how I see it, I'm sure a more experienced programmer will tell me else wise) how will it know a new cable was added, or an emitter? It's easy to tell if a cable was removed (posted a cleanMap method) but what about subtle additions?

[TheEpicTekkit]

Maybe, if a new cable, emitter, or requester is added, and it connects to a cable in the network, that cable will be the one that realizes that the network is not up to date (can use onNeighborBlockChange(...) {...} method to detect this), and so will trigger a refresh of the network. So, what I plan to do, is have every block in the network (including the cables) remember the coordinates of all the other blocks in the network. So with this, if a cable realizes that the network is not up to date, it will notify the rest of the network. Also, maybe every so often (probably every minute, possibly every 20 seconds, depending on how much lag a refresh causes), the network automatically refreshes itself. This is because other mods mechanics such as blockbreakers may not trigger a block update for some strange reason, or maybe just a sync glitch may cause it not to realize that the network has changed.

[TheEpicTekkit]

Okay, so I have came across an interesting problem that I didn't think of before. How do I store all the data in the network? I can't have each block store the network, because they each would have a seperate instance of the network, and this would cause problems with node ids (the nodes in the network are assigned an ID, this is what the pathfinder uses to know what node it is going from, and what node it is going to.) So how would I store the network data as one object? I cant use static fields, because there can be multiple networkes in the world at the same time, and they will most likely each be different.

[TheGreyGhost]

Hi

 

I don't think it's a good idea to have each block remember the coordinates of all other blocks in the network.  This will very quickly lead to huge memory requirements and become very slow to update.

 

For example - if your network has 100 blocks, each one has to remember 99 coordinates, so that's 9900 coordinates.  You're effectively storing the same information 100 times.  If your network has 200 blocks, that's 39800 coordinates to remember.  1000 blocks becomes 999,000 coordinates.

Use a collection of Graphs instead, one Graph per network, and use your A star algorithm on those.  You might need to add a game mechanic to make sure the networks stay a reasonable size (for example - maximum of 100 blocks per network, or a block can't below to a network if it is more than 64 blocks from the far side).

 

You can store the networks anywhere you like, i.e. in one of your own classes, so long as you save them and reload them with the world.  You can use your own custom save files for that or alternatively in a TileEntity NBT (for example - if you add the rule that a network can have at most one power source) or in per-world storage (see this link for more ideas... (assuming it's still the same for 1.7.10) http://www.minecraftforge.net/forum/index.php?topic=8520.0)

 

-TGG

 

[hugo_the_dwarf]

I guess could do it with another block called a "fuse panel" or "circuit box" that will do the mapping and routing and hold the lists, then nearby machines, nodes, emitters will look for this controller. And have something that if another fuse box is placed too close it simply does nothing to prevent the same list from being populated (this will help stop griefer's from abusing your mod to ruin servers.)

[TheEpicTekkit]

So, Hugo, your idea is basically to make it like a multiblock, and the fuse box is the controller? I thought of this before, but not too sure about it. TGG's idea I think is better.