Jump to content
  • Advertisement
Sign in to follow this  
tajny

Finding points on path every distance

This topic is 2477 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all

i have problem with one thing in my game , maybe someone will help me out.

I have a array of points which creates path for my player.

ArrayList<PointF> mINPUT = new ArrayList<PointF>();
mINPUT.add(new PointF(15, 10));
mINPUT.add(new PointF(100, 10));
mINPUT.add(new PointF(350, 10));
mINPUT.add(new PointF(410, 10));



What im trying to do is find points on that path every distance like on the image where distance is chunk size
[attachment=7484:chunk.jpg]

Sometime chunk will be longer than each line , other time it will be breaked on two subpaths

I have tried with this method but without luck


public ArrayList<PointF> getPositions(ArrayList<PointF> mInput,float mChunkSize){
ArrayList<PointF> mResult = new ArrayList<PointF>();
float mModuloDistance = 0f;
for (int i = 0;i<mInput.size()-1;i++){
//distance to next
float mDistanceAB = MyGameMath.distance(mInput.get(i).x, mInput.get(i).y,mInput.get(i+1).x,mInput.get(i+1).y);
//how many parts will fit
float mCountParts = (float) (mDistanceAB/mChunkSize); //how much parts will fit
//if distance is greater than chunk size

if (mCountParts>0){
if (Math.abs(mDistanceAB)>mChunkSize) {
Log.i("Chunk","Index "+(i)+" -> "+(i+1)+" = "+mCountParts+", rest="+mModuloDistance);

float mStartingPointX = mInput.get(i).x;
float mStartingPointY = mInput.get(i).y;

float dx = mInput.get(i+1).x-mStartingPointX;
float dy = mInput.get(i+1).y-mStartingPointY;
float ux = dx/mDistanceAB;
float uy = dy/mDistanceAB;
for (int y=0;y<=mCountParts;y++){
//for every part
float nx = mStartingPointX+ux*mChunkSize*y;
float ny = mStartingPointY+uy*mChunkSize*y;

mResult.add(new PointF(nx, ny));// Log.i("Chunk","at:"+nx+","+ny);
}
}
}
mModuloDistance = mDistanceAB%mChunkSize; //how much left from previous subpath
}
return mResult;
}


Thanks in advance
Paul

Share this post


Link to post
Share on other sites
Advertisement
The function trace_path below does what I think you want, and it should be fairly readable. The rest is support code.

#include <iostream>
#include <cmath>
#include <vector>

struct Vector2D {
double x, y;

Vector2D(double x, double y) : x(x), y(y) {
}
};

Vector2D operator+(Vector2D v, Vector2D w) {
return Vector2D(v.x+w.x, v.y+w.y);
}

Vector2D operator-(Vector2D v, Vector2D w) {
return Vector2D(v.x-w.x, v.y-w.y);
}

Vector2D operator*(double s, Vector2D v) {
return Vector2D(s*v.x, s*v.y);
}

Vector2D operator*(Vector2D v, double s) {
return s*v;
}

double dot_product(Vector2D v, Vector2D w) {
return v.x*w.x + v.y*w.y;
}


double length(Vector2D v) {
return std::sqrt(dot_product(v, v));
}

struct Point2D {
double x, y;

Point2D(double x, double y) : x(x), y(y) {
}
};

Point2D operator+(Point2D p, Vector2D v) {
return Point2D(p.x+v.x, p.y+v.y);
}

Vector2D operator-(Point2D p, Point2D q) {
return Vector2D(p.x-q.x, p.y-q.y);
}

std::ostream &operator<<(std::ostream &os, Point2D p) {
return os << '(' << p.x << ',' << p.y << ')';
}

double distance(Point2D p, Point2D q) {
return length(p-q);
}


void trace_path(std::vector<Point2D> const &v, double step) {
int i = 0, end = v.size();
double edge_length = distance(v, v[i+1]);
double how_far_along_edge = 0.0;

while (1) {
double to_go = step;
while (to_go > edge_length - how_far_along_edge) {
to_go -= edge_length - how_far_along_edge;
++i;
if (i == end) return; // At the end of the path
edge_length = distance(v, v[i+1]);
how_far_along_edge = 0.0;
}
how_far_along_edge += to_go;

Point2D p = v + (how_far_along_edge/edge_length)*(v[i+1]-v);

std::cout << p << '\n';
}
}


int main() {
std::vector<Point2D> path;
path.push_back(Point2D(0.0, 0.0));
path.push_back(Point2D(5.0, 0.0));
path.push_back(Point2D(3.0, 4.0));
path.push_back(Point2D(7.0, 4.0));
path.push_back(Point2D(0.0, 0.0));

trace_path(path, 1.0);
}

Share this post


Link to post
Share on other sites
It works! Thanks

Here is implementation in Java



public ArrayList<PointF> [color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

trace_path

[/font](ArrayList<PointF> mInput,float step){
int i = 0;
ArrayList<PointF> mOutput = new ArrayList<PointF>();
int end = mInput.size()-1;
float edge_length = distance(mInput.get(i).x, mInput.get(i).y,mInput.get(i+1).x,mInput.get(i+1).y); //pythagoras
float how_far_along_edge = 0.0f;
while(true){
float to_go = step;
while (to_go > edge_length - how_far_along_edge) {
to_go -= edge_length - how_far_along_edge;
++i;
if (i == end) return mOutput; // At the end of the path
edge_length = MyGameMath.distance(mInput.get(i).x, mInput.get(i).y,mInput.get(i+1).x,mInput.get(i+1).y);;
how_far_along_edge = 0.0f;
}
how_far_along_edge += to_go;
float nx = mInput.get(i).x + (how_far_along_edge/edge_length)*(mInput.get(i+1).x-mInput.get(i).x);
float ny = mInput.get(i).y + (how_far_along_edge/edge_length)*(mInput.get(i+1).y-mInput.get(i).y);
mOutput.add(new PointF(nx, ny));

}
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!