A pathfinding solution

Processing
1

Hi everybody, i ask my first question here and i recived great help, so here is my second question.
i have creatures who move randomly for now, if they find the food they eat ect…
but now i want to make some “water sources” and when my creatures need water they go to the nearest and drink.
And the problemes begin here, i cant find a way to code a behavior where a creature choose between 3 (or more) differents water sources at different locations. Like the creature move randomely and at a moment she need water and she had to choose the nearest water source between 3 or more.

I know i ask a lot whit this question but i looked a lot in the web and i cant find a solution.

thank you for yours times and have a nice day.

1 Like
2

Hi,

Can you tell a bit more about your program ?

Right now it seems that all you need to do is compute the distance from your creature to the 3 water sources, select the closest one and then make your creatures go there in a straight lines.

Why do you wanna use a pathfinding algorithm ? Is there some obstacles to avoid ?

3

well i used the word pathfinding because i was thinking its the best way, sorry if i used it wrong.

I follow the book “the nature of the Code” by Daniel Schiffman. And i write it with java on Eclipse.

for now i have 2 class of herbivor (the Male and the Female) who move randomly around the map ( just a screen for now), 2 other class for the trees and their fruits. there is no obstacles to avoid.

and yes thats what i was thinking, a way to compute the distances and then choose the shortest, but i dont know how.

4

I guess that your simulation is pixel based.

In that case, what I would do is to store each pixel of the edge of each water sources in an array when you create the sources.

That way you have access to all the places where you creatures can go have a drink.

Then you just have to run through all those locations and compute the distance between them and your creatures. No need for square roots (time consuming) you can just compute d = x² + y².

You find the smallest one and this is your creature target.

5

yes its pixel based.

ok thats a good way i allready store the pixel edge for my creatures and for the food.
Sorry if i look stupid,
when you said d = x² + y² , what do you mean ?
d (distance one) = (herbivor.x + water1.x) + (herbivor.y + water1.y) am i correct ?
and how do i compute to find the shortest ?

6

Also look at dist() which is the same like the formula above

So for loop over the lakes and store the number of the lake with the smallest distance to the herbivores.

float distMy = dist( herbiv.x, herbiv.y,
lake1X, lake1Y);

7

Almost,

d (distance) = (herbivor.x - water.x)² + (herbivor.y - water.y)²
That is simply the pythagorean theorem but without the square-root :

To compute the smallest one you need a variable to store the current smallest. In macro code in would be something like this :

int currentSmallest = height * height + width * width; // You initialize that variable with the biggest distance you can found AKA the diagonal length of your canvas

for each waterPixel in waterEdgePixels { //You go through all your water edge pixels
  d = (creature.x - waterPixel.x)² + (creature.y - waterPixel.y)²; //You compute the distance to your creature
  if (d < currentSmallest) { // If the distance is smaller than the smallest that you found before then you found a new smallest
    currentSmallest = d;
  }
}
8

Mind to post your entire code on GitHub?

9

ok thanks a lot guys i gonna try, and i will respond with the code i wrote.

10

well it seems stupid but i dont know how :confused:
i just started programming few month ago

11

ok i think i have done it for github :

12

Thanks a ton! Chrisir

13

hi sorry for the long silence, i dont have a lot of day off and i do programing in my free time.

i tried your solution guys but i have a problem and i cant manage it.

for now thats my code:

the world: (where i launch everything)

float currentSmallest = (parent.height * parent.height) + (parent.width * parent.width);
		float d;
		float target;
		for(int a = carn1m.size()-1; a >= 0; a--){
			for(int b = lac.size()-1; b >= 0; b--){
				Carnivor1M c1m = carn1m.get(a);
				Lac l = lac.get(b);
				d = ((c1m.position.x - l.position.x) * (c1m.position.x - l.position.x)) + ((c1m.position.y - l.position.y) * (c1m.position.y - l.position.y));
				
				
				if(d < currentSmallest){
					currentSmallest = d;
					target = currentSmallest;
					
					
					//c1m.arrive(target);
				}
			}
		}

my water source :

public class Lac {
	PApplet parent;
	
	ArrayList<PVector> lac;
	
	public PVector position;
	
	
	
	@SuppressWarnings("deprecation")
	public Lac(PApplet p,PVector l){
		
		lac = new ArrayList<PVector>();
		parent = p;
		position = l.get();
		
	}
	
	@SuppressWarnings("deprecation")
	public void add(PVector l){
		lac.add(l.get());
	}
	
	void update(){
		parent.stroke(1);
		parent.fill(0,182,210);
		parent.ellipse(position.x, position.y, 50, 50);
	}
	
	public void run(PApplet p){
		update();
	}
	
	public ArrayList<PVector> getLac(){
		return lac;
	}
}

and my creatur for the test :

public class Carnivor1M {
	PApplet parent;
	ArrayList<PVector> carn1m;
	
	public PVector position;
	DNA2 dna2;
	float xoff;
	float yoff;
	
	////////////variables genetiques
	float health;
	float r; ///la taille
	float maxspeed;
	
	int lastChildTime = -1;
	
	
	float maxforce;
	PVector acceleration;
	PVector velocity;
	
	@SuppressWarnings("deprecation")
	public Carnivor1M(PVector l, DNA2 dna2_, PApplet p){
		carn1m = new ArrayList<PVector>();
		
		parent = p;
		position = l.get();
		xoff = p.random(1000);
		yoff = p.random(1000);
		
		dna2 = dna2_;
		health = PApplet.map(dna2.genes[0], 0, 1, 50, 250);
		r = PApplet.map(dna2.genes[0], 0, 1, 10, 25);
		maxspeed = PApplet.map(dna2.genes[0], 0, 1, 10, 1);
		
		acceleration = new PVector(0,0);
		velocity = new PVector(0,0);
		maxforce = (float) 0.1;
		
	}
	
	void update(){
		float vx = PApplet.map(parent.noise(xoff), 0, 1, -maxspeed, maxspeed);
		float vy = PApplet.map(parent.noise(yoff), 0, 1, -maxspeed, maxspeed);
		PVector velocity = new PVector(vx,vy);
		xoff += 0.01;
		yoff += 0.01;
		position.add(velocity);
		//health -= 0.1;
	}
	
	void borders(PApplet p){
		if (position.x < -r) position.x = p.width+r;
	    if (position.y < -r) position.y = p.height+r;
	    if (position.x > p.width+r) position.x = -r;
	    if (position.y > p.height+r) position.y = -r;
	}
	
	void display(){
		parent.ellipseMode(PConstants.CENTER);
		parent.strokeWeight(2);
		parent.stroke(0,0,0, health);
		parent.fill(213, 0,0, health);
		parent.ellipse(position.x, position.y, r, r);
	}
	
	public DNA2 getDNA2(){
		return dna2;
	}
	
	public float getR(){
		return r;
	}
	
	public ArrayList<PVector> getCarnivor1M(){
		return carn1m;
	}
	
	public void run(PApplet p){
		update();
		borders(parent);
		display();
	}
	
	void applyForce(PVector force){
		acceleration.add(force);
	}
	
	public void arrive(PVector target){
		PVector desired = PVector.sub(target, position);
		float d = desired.mag();
		if(d < 100){
			float m = PApplet.map(d, 0, 100, 0, maxspeed);
			desired.setMag(m);
		}
		else{
			desired.setMag(maxspeed);
		}
		PVector steer = PVector.sub(desired, velocity);
		steer.limit(maxforce);
		applyForce(steer);
	}
	
}

so here is my problem: i need to turn the pythagorean theorem that jb4x explain to me into a PVector.
I have my float for the currentSmallest, the d and the target.
But when i launch c1m.arrive (my creature test) i need a PVector and not a float and i dont know how.

I think its not a good idea to change the creature or water source class, i tried and it come really mess up really fast.
can you help me find a solution ?

Thanks again for your times guys.

14

Hey,

Please format your code: select all the code you pasted and then click on the icon </>.
You can edit your post by clicking the small pen on the bottom right of your post.

Also try to transform your problem into a small example that anyone can try and understand completely, right now we need to understand all of your code to help you.

For you problem I think you are messing up the currentSmallest thingy.
You have actually two things:

  • the smallest distance that you found
  • and the pixel that correspond to that smallest distance

You need to keep track of both of them.

15

Hi
your target should indeed not be a float.
Instead try something like this:

d = ((c1m.position.x - l.position.x) * (c1m.position.x - l.position.x)) + ((c1m.position.y - l.position.y) * (c1m.position.y - l.position.y));
if (d < currentSmallest) {
	currentSmallest = d;
	target = new PVector(l.position.x, l.position.y);
}

which is the x,y of the last water source you checked when the distance was the smallest.

16

hi, i format my code, sorry i dont have all the good reflex yet.

well i think my problem can be resume with one part of code :

float currentSmallest = (parent.height * parent.height) + (parent.width * parent.width);
float d;
//float target;
for(int a = carn1m.size()-1; a >= 0; a--){
	for(int b = lac.size()-1; b >= 0; b--){
		Carnivor1M c1m = carn1m.get(a);
		Lac l = lac.get(b);
		d = ((c1m.position.x - l.position.x) * (c1m.position.x - l.position.x)) + ((c1m.position.y - l.position.y) * (c1m.position.y - l.position.y));
				
				
		if(d < currentSmallest){
			currentSmallest = d;
			//target = currentSmallest;
			PVector target = new PVector(l.position.x, l.position.y);
					
			c1m.arrive(target);
		}
	}
}

carn1m is my creature and lac is my water source. There are three different water sources on the map and one creature, no wall or something that can block the creature.

i need to find a way to check the positions of the three water source and the position of my creature.
then find wich of the water sources is the nearest of the creature and say its the target of my creature.

17

Thanks for formatting your code :slight_smile:

Now you keep track of both the smallest distance and the pixel that correspond to that smallest distance so everything should be okay for this matter.

I have the feeling that you are calling the arrive() method at the wrong moment however.
I presume it is that method that makes your carnivor move to the target. In this case you want it to be outside you second loop. You first want to loop through all the outside lake pixels and only then, when you found the nearest one, you want to make your carnivor move towards it.

18

yes the arrive() method make my creature move to the target.

but now i think thats the problem is my target im not sure that its store the closest water source.
When i run my code, it work (ouf :slight_smile: ) but my creature dont move to the closest.

my arrive() methode is based on the code wroted by Daniel Shiffman :


i didnt make a change, i just wrote it on java

19

Again, try to move your arrive() methode outside your for loop:

float currentSmallest = (parent.height * parent.height) + (parent.width * parent.width);
float d;

for(int a = carn1m.size()-1; a >= 0; a--){
    Carnivor1M c1m = carn1m.get(a); //Change here
	for(int b = lac.size()-1; b >= 0; b--){
		Lac l = lac.get(b);
		d = ((c1m.position.x - l.position.x) * (c1m.position.x - l.position.x)) + ((c1m.position.y - l.position.y) * (c1m.position.y - l.position.y));
						
		if(d < currentSmallest){
			currentSmallest = d;
			PVector target = new PVector(l.position.x, l.position.y);
		}
	}
    c1m.arrive(target); //And change here
}
20

ok i wrote it like you said and now its work properly, amazing ! i found the other problem, my creature had a random mouvement in his update() methode and of course its override the arrive() methode.

I can manage that problem myself i think :slight_smile:

jb4x thank you again, i was afraid i cant manage this issue for the end of the week but now i can move forward !

i gonna update my github when i make my changes.

A BIG thank you again.

1 Like