Skip to main content
GameDev.net gamedev.net
🔒 Locked

Funnel Algorithm

Started by Antonym Sep 18, 2009 at 5:41 AM 4 replies 5.6k views
Original Post
Antonym
Antonym
Hello I've been searching for any material regarding the implementation of the funnel algorithm. The best explanation I've found is http://www.cs.ualberta.ca/~mburo/ps/thesis_demyen_2006.pdf Page 52. I start with my apex at the start point and a funnel structure storing the left and right vertices of the first edge in the channel(In separate arrays/vectors?). I go on to check each edge's vertices adding each vertex depending on its side. It says:
Quote:
Vertices are popped from that side of the funnel until the wedge in which the current vertex lies is discovered, at which point that vertex is added to the end of the funnel deque on that side.
Here's where I get confused. Do I pick the first vertex and go on to pop vertices until the wedge in which the picked vertex is found? (Also how do I find this 'wedge'?) Then go on to repeat the process with that vertex? If the apex is popped in this manner then vertex becomes the new apex. Each apex is a point in the new path?
Zakwayda
Zakwayda
Ah, the funnel algorithm. Only have time for a quick reply at the moment, but here are some quick comments:

First of all, yes, when a new apex is found, it's added as a new point on the path.

As for storing the funnel, rather than using a separate container for each side, you'll want to use a single container - the most logical choice for this is probably a double-ended queueu (in C++, for example, you might use std::deque).

It might be helpful to draw some examples and work through the algorithm step by step in order to fully understand what's going on. Keep in mind that each funnel side should represent the shortest path from the apex to the leading (i.e. most recently added) vertex on that side (another way to think of this is that the funnel side should always be inward convex). Roughly speaking, whenever you add a new vertex, you then want to remove all vertices that cause this convexity constraint to be violated.

Ok, this was not a very good post - it's early, and I'm not entirely sure I got everything right :| I hope it'll be at least somewhat helpful though.
Antonym
Antonym
Quite helpful although the implementation is still giving me trouble.
I'll post what I've put so far while I continue to try to figure out.

Code removed.

[Edited by - Antonym on September 20, 2009 2:19:05 AM]
Antonym
Antonym
Looking at the pseudocode I've come with an approximation of it but I am confused about several things. I've commented some of the lines of code.

I've tried to manage the deque with several iterators. Pushing front the left vertices and back the right ones. The apex(tracked with an iterator) is set to the first vertex added and is changed each time it's popped. 

enum sideType{LEFT_SIDE,RIGHT_SIDE,POINT_SIDE};struct FunnelDeque{	std::deque<b2Vec2> fdeque;	std::deque<b2Vec2>::iterator apex;	sideType apexType;	FunnelDeque(b2Vec2 s){AddLeft(s);AddRight(s);apex = fdeque.begin();apexType = POINT_SIDE;}	std::deque<b2Vec2>::iterator Left(){return fdeque.begin();}	std::deque<b2Vec2>::iterator Right(){return fdeque.end() - 1;}	std::deque<b2Vec2>::iterator Apex(){return apex;}	sideType ApexType(){return apexType;}	void AddLeft(b2Vec2 v){fdeque.push_front(v);}	void AddRight(b2Vec2 v){fdeque.push_back(v);}	void PopLeft(){fdeque.pop_front();}	void PopRight(){fdeque.pop_back();}	void PopApexLeft(){apex += 1; apexType = RIGHT_SIDE;}	void PopApexRight(){apex -= 1; apexType = LEFT_SIDE;}};struct Path{	std::vector<b2Vec2> path;	void Add(b2Vec2 v){path.push_back(v);}};


Path ShipEnemy::Funnel(std::vector<b2Vec2> c, b2Vec2 s, b2Vec2 g){	Path p; 	b2Vec2 vl,vl_,vr,vr_;	int NumEdges = c.size()/2;	if(NumEdges < 1){		p.Add(s);p.Add(g);		return p;	}	AddVertex(s,p);/*Do I simply add the start to the path?*/	FunnelDeque f(s);	vl = c[0]; Add(f,vl,LEFT_SIDE,p);	vr = c[1]; Add(f,vr,RIGHT_SIDE,p);	for(int i = 2; i < NumEdges;){		vl_ = c; vr_ = c[i + 1];		if(vl == vl_){ /*Won't this cause vertices to become skipped?*/			vr = vr_; Add(f,vr,RIGHT_SIDE,p);		}		else{			vl = vl_; Add(f,vl,LEFT_SIDE,p);		}	}	Add(f,g,POINT_SIDE,p);	return p;}void ShipEnemy::Add(FunnelDeque &f, b2Vec2 v, sideType t, Path &p){	float a0,a1,a2;	if(t == LEFT_SIDE){		while(1){			if(f.Left() == f.Right()){				f.AddLeft(v);				break;			}			else if(f.Left() == f.Apex()){				a0 = Angle(*(f.Left()), *(f.Left() + 1)); /*Won't this access a vertex on the other(right) side causing a problem?*/				a1 = Angle(*(f.Left()), v);			}			else{				a0 = Angle(*(f.Left() + 1), *(f.Left()));				a1 = Angle(*(f.Left()), v);			}			if(CounterclockwiseTo(a0,a1)){/*I am not sure how to perform this test*/				f.AddLeft(v);				break;			}			if(f.Left() == f.Apex()){				a2 = Angle(*(f.Apex()),f.ApexType(),*(f.Apex() + 1), RIGHT_SIDE);				AddVertex(*(f.Apex()),p);				f.PopApexLeft();			}			f.PopLeft();		}	}//Right side repeat	else if(t == POINT_SIDE){		int i = 0;		while(f.Apex() + i != f.Right()){			i = i + 1;			AddVertex(*(f.Apex() + i), p);		}	}}float ShipEnemy::Angle(b2Vec2 v1, b2Vec2 v2){	b2Vec2 v = v2 - v1;	return atan2(v.y,v.x);}float ShipEnemy::Angle(b2Vec2 v1, sideType apexT, b2Vec2 v2, sideType t){/*...???...*/}bool ShipEnemy::CounterclockwiseTo(float a0,float a1){/*...???...*/}void ShipEnemy::AddVertex(b2Vec2 v, Path &p){	p.Add(v);//?}


Putting this half-baked attempt aside.

I think it'd be best as you mentioned to break this down into simpler steps(I seem to be getting in way over my head) and approach each one individually. I don't see how to decompose this algorithm though. What should I try doing first?

[Edited by - Antonym on September 20, 2009 9:28:04 AM]
Zakwayda
Zakwayda
Hm, wish I could be more helpful, but to figure out what's wrong I'd really have to dig into your code (and I've got my hands full with my own code!).

Here's a suggestion though. When I was implementing this I found it helpful to draw out some example cases on paper and work through them a step at a time. Another thing you could do would be to create a test application that allows you to step through the algorithm, and that displays at each step the current state (path, apex, funnel sides, etc.). If you could step through the algorithm and see what's happening at each step, I imagine it would be a lot easier to see where things are going wrong.

[Looks like you edited your post while I was posting, but I think the suggestions I made probably still apply :)]
Antonym
Antonym
It's finally done ^_^! Gonna leave my code here in case someone else too stumbles into this nightmare. It may be a little messy cause I didn't really thought it through, may update later on with a cleaner version.

channel1 contains all vertices in the right side of the funnel and channel2 contains all on the left.
Apex will contain the completed path.
s = start, g = goal.
fright and fleft are vectors to store temporarily vertices on each side of the funnel to be processed. 

Path ShipEnemy::Funnel(b2Vec2 s, b2Vec2 g){	b2Vec2 vl,vr, s1,s2;	apex.push_back(s);	bool update;	std::vector<b2Vec2>::iterator u;	for(int i = 0; i < channel1.size(); i++){		vr = channel1;		update = false;		if(fright.empty()){//Other side isn't empty			fright.push_back(vr);			update = true;		}		else if(vr.x != fright.back().x ||			vr.y != fright.back().y){//Don't add duplicates			fright.push_back(vr);			update = true;		}		u = fright.begin(); 		if(update && fright.size() >= 3){			while(u < fright.end() - 2){				s1 = *(u + 1) - *(u);				s2 = *(u + 2) - *(u + 1);								if(b2Cross(s1,s2) >= 0){//b2Cross is the perp dot product, test is s2 is clockwise with respect to s1					fright.erase(u + 1);					u = fright.begin();				}				else					u++;			}			if(u == fright.begin() &&				fleft.size() > 1){//If we are at the current apex				s1 = *(u + 1) - *(u);				s2 = *(fleft.begin() + 1) - *(u);				if(b2Cross(s1,s2) <= 0){//Check if first left segment(s2) is counterclockwise with respect to first right segment(s1)					apex.push_back(*(fleft.begin() + 1));//Make first segment in the other side the new apex.					fright.erase(u);					fleft.erase(fleft.begin());					fright.insert(fright.begin(),*fleft.begin());					u = fright.begin();				}			}		}/*Simply reverse some of the values(fleft to fright and vice versa and the clockwise test*/       }}


[Edited by - Antonym on September 21, 2009 10:46:03 PM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.