1
\$\begingroup\$

I am trying to perform a weighted cascade down a path in a 3D environment. Now, what I am trying to do is have one object(a cube) in the environment scan from its coords 1 in every direction for another cube, and then if it finds another cube, it will scan around that cube for another cube etc all the way to the end of the path, or it has reached its limit of 40 cubes, and I would like it to have a weight for each step down the path it takes so it will stop if it has travelled more than 40 cubes down the path.

Now, I have no idea on where to go from scanning directly around the first cube. How do I make it move onto the next cube, then the next cube, then the next etc without writing a really long method that considers each cube along the path?

Before pathfinding algorithms such as A-Star or BFS/DFS come into this, I have already tried that and found it way too complicated, it was unnecessary complicated just for this one part of my program.

Thanks.

Edit: I forgot to mention that these cubes do not move, they stay wherever the player puts them.

\$\endgroup\$
8
  • \$\begingroup\$ To avoid a "very long method," you can use a loop. What you describe is basically DFS. \$\endgroup\$ Commented Sep 30, 2014 at 20:11
  • \$\begingroup\$ That is what I am trying to do, but am getting confused and stuck on. I just end up getting "stackOverflowError" because the method is constantly getting repeated, or it can only find cubes directly adjacent to it, and doesn't actually scan down the whole path. \$\endgroup\$ Commented Sep 30, 2014 at 20:21
  • \$\begingroup\$ Though, to be honest, I don't really understand A-Star, DFS and BFS, I know that A-Star requires a destination and an origin (I have played around with this algorithm a lot more than DFS and BFS), I know DFS goes as deep into the path as it can before backtracking to a point in the path where it could take a different route, and I am not too sure about BFS at all. So, do you think I should go with DFS? I haven't really used it much at all, I have mostly been trying A-Star as I know it the best out of the three. \$\endgroup\$ Commented Sep 30, 2014 at 20:26
  • 1
    \$\begingroup\$ It sounds like you're using a recursive function (which makes sense, because this is a naturally recursive problem). Recursion, when tail-recursion cannot be used, has the problem of maximum stack depth. You can replace any recursive algorithm with an iterative version to avoid stack depth problems. \$\endgroup\$ Commented Sep 30, 2014 at 20:26
  • \$\begingroup\$ Oh, I see how that works now. that solves one problem. Now the problem I had though was scanning around the next cube in the path. And the way I was doing it was by triggering the method in the first cube once, then if the first cube finds another cube, it gets its coords, and then casts its superclass to the instance of the cube it has found, this is hard to explain, and I hope it makes sense, but basically this gets the cube it has found. From there, as both cubes are the same, it triggers the search method from that cube and marks itself as scanned. \$\endgroup\$ Commented Sep 30, 2014 at 20:46

1 Answer 1

Reset to default
1
\$\begingroup\$

you say it's so complicated to implement a path-finding algorithm, but it isn't...

and what's even better, once you have implemented one you can use that algorithm whenever needed again...

i can provide you with an simple one (A* it is - and it is easy) and it's so open you can use it on hexfields, squared fields or even on cubes...

private ArrayList<Node> oList = new ArrayList<Node>(); //open list private ArrayList<Node> cList = new ArrayList<Node>(); //closed list public ArrayList<Point> getShortestPath( Point startPoint, Monster walker, StaticMap map, Point targetPoint, int maxPathLength) { int xs = startPoint.x; int ys = startPoint.y; //int zs = startPoint.z; int xe = targetPoint.x; int ye = targetPoint.y; //int ze = targetPoint.z; oList.clear(); cList.clear(); Node start = new Node(xs,ys); //Node start = new Node(xs,ys, zs); // Node end = new Node(xe, ye); //Node end = new Node(xs,ys, zs); // oList.add(start); boolean noWayFound = false; while(true){ Node current = getLeastF(oList); if (current == null){ noWayFound = true; break; } if (current.isSamePos(end) ){ noWayFound = false; end.from = current.from; break; } //this is just an abortion criteria if you can't //guarantee a shortest path if (current.g > maxPathLength*10){ noWayFound = true; break; } oList.remove(current); cList.add(current); expandNode(current, map, walker, end); } ArrayList<Point> path = new ArrayList<Point>(); if (!noWayFound){ Node n = end; while(n != null){ path.add(new Point(n.x, n.y) ); //path.add(new Point(n.x, n.y, n.z) ); n = n.from; } } return path; }

what's different on any map is expandNode ... this implementation depends on your map... it looks at the current node and looks into all neighbours (4 on a real squared map, 8 on a semi squared map, 6 on a hex map and also 6 on a 3d squared map )...

private void expandNode(Node current, StaticMap map, Monster walker, Node end) { Node nNode = new Node(current.x, current.y-1); Node eNode = new Node(current.x+1, current.y); Node sNode = new Node(current.x, current.y+1); Node wNode = new Node(current.x-1, current.y); //Node upNode = new Node(current.x, current.y, current.z-1); //Node nownNode = new Node(current.x, current.y, current.z+1); if (checkIsPassable(nNode, walker, staticMap) ){ //true if you can go north addIfRequired(nNode, current, end, 10); //10 is the walking cost } if (checkIsPassable(eNode, walker, staticMap) ){ addIfRequired(eNode, current, end, 10); } if (checkIsPassable(sNode, walker, staticMap) ){ addIfRequired(sNode, current, end, 10); } if (checkIsPassable(wNode, walker, staticMap) ){ addIfRequired(wNode, current, end, 10); } //if (checkIsPassable(upNode, walker, staticMap) ){ // addIfRequired(upNode, current, end, 10); //} //if (checkIsPassable(downNode, walker, staticMap) ){ // addIfRequired(downNode, current, end, 10); //} }

the last point is to add a field (a cube) if required ^^

private void addIfRequired(Node nNode, Node current, Node end, int distance) { if ( !isPosInList(nNode, cList) ){ if ( isPosInList(nNode, oList) ){ Node can = getPos(nNode, oList); if (can.g < nNode.g){ can.from = current; can.g = current.g + distance; can.f = can.h + can.g; } }else{ nNode.from = current; nNode.h = 10* ( Math.abs(end.x-nNode.x)+Math.abs(end.y-nNode.y) ); //nNode.h = 10* ( Math.abs(end.x-nNode.x)+Math.abs(end.y-nNode.y) +Math.abs(end.z-nNode.z) ); nNode.g = current.g + distance; nNode.f = nNode.h + nNode.g; oList.add(nNode); } } }

if you're wondering what a node is..

public class Node { int f; int g; int h; int x; int y; //int z; Node from; Node(int x, int y){ this.x=x; this.y=y; } //Node(int x, int y, int z){ // this.x=x; this.y=y;this.z=z; //} boolean isSamePos(Node n){ if (n != null && n.x==x && n.y==y) return true; //if (n != null && n.x==x && n.y==y && n.z==z) return true; return false; } @Override public String toString() { return ""+x+"/"+y+" g="+g+" h="+h+" f="+f; //return ""+x+"/"+y+"/"+z+" g="+g+" h="+h+" f="+f; } }

this would be the a*algortihm for path finding.... i've added in comments //... how you have to adjust that code for 3D path finding...

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.