Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Pathfinding Algorithm
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Raknarg




PostPosted: Wed Jun 13, 2012 1:36 pm   Post subject: Pathfinding Algorithm

Im attempting to write a simple Tower Defense for my class. However, I ran into a problem.

Lets say you have an open field. Your enemies can walk through this field to get to the exit. You can place towers in this field which attack and also act as obstacles. The thing is that these enemies can always find the shortest path no matter how you arrange the obstacles. Think of it like desktop Tower Defense or something.

I can only think of two things I can use: Direction based on proximity to exit and brute force. They both have problems though. In an open field, the proxitmity based one would easily find the shortest path, or a very short path and do it quickly. However, it'll make errors the more the the field becomes a maze. The recursive brute force one would be able to solve a maze easily, but it would take way too long in an open field. i don't know how I would mix the two or anything.

Suggestions?
Sponsor
Sponsor
Sponsor
sponsor
crossley7




PostPosted: Wed Jun 13, 2012 4:38 pm   Post subject: RE:Pathfinding Algorithm

I'm going to assume you have some sort of grid to represent your field in your data structure. from this, run a BFS from the end to the start and whenever a new obstacle is placed, readjust just that part of the bfs. This will require you to keep a copy of the array with distances from the end in your program but will save you a lot of time only calculating part of the array.
Raknarg




PostPosted: Wed Jun 13, 2012 8:13 pm   Post subject: RE:Pathfinding Algorithm

Sorry, you'll have to explain that term (bfs)

And yeah, it's just a simple grid map
Raknarg




PostPosted: Wed Jun 13, 2012 9:45 pm   Post subject: RE:Pathfinding Algorithm

Actually, I discovered that bruteforcing seems to work fine on something this simple, I guess I'll just use that
crossley7




PostPosted: Thu Jun 14, 2012 9:59 am   Post subject: RE:Pathfinding Algorithm

bfs is essentially brute force. It stands for breadth first search and will just calculate outwards from a starting point until it has reached the end or you tell it to stop. It is designed to do exactly what you want and you are probably already using it without knowing what it is called.


Here is the link to clarify what I was suggesting.
http://en.wikipedia.org/wiki/Breadth-first_search

The rest of my suggestion was just to find a way to only have to do part of the search every time you place a new tower. However with a grid under about 100x100 you can just run the whole search regularly without much of a loss in performance (10,000 operations takes essentially no time in many languages)
Raknarg




PostPosted: Thu Jun 14, 2012 11:52 am   Post subject: RE:Pathfinding Algorithm

Yeah, my teacher suggested something like that, I might change it to that later.

I only have something like a 20*20 grid, so yeah it's not really slow at all. I wasn't really looking for it for effectiveness, I just wanted to make the most elegant solution for learning and stuff. Thanks for that, I'll look into it.
mirhagk




PostPosted: Thu Jun 14, 2012 3:08 pm   Post subject: RE:Pathfinding Algorithm

If it were to be more complex and you wanted to be more effective you should research A*, which is basically the next step up from bfs), but as crossley mentioned you won't come across an issue unless your map gets to sizes like 10 000 x 10 000 (even at 1000 x 1000 you might consider it if it happens a lot)
Raknarg




PostPosted: Thu Jun 14, 2012 6:25 pm   Post subject: RE:Pathfinding Algorithm

Actually, i did look into A* but it seems that it'll make mistakes when it looks for a path. For instance there might be one path which seems to be closer in proximity, but the other branch actually gets there faster in the end. Because it doesnt look into all the paths, it cannot tell teh difference.

Maybe I just read it wrong.
Sponsor
Sponsor
Sponsor
sponsor
mirhagk




PostPosted: Fri Jun 15, 2012 9:08 am   Post subject: RE:Pathfinding Algorithm

Yes you must have read it wrong. Proper A* with a proper heuristic will always find the best path.

It's basically the same as breadth first search, but when you calculate how far you've travelled in each path, you include a guess of how far you need to travel to get there. As long as that guess never underestimates it will always find the best route. The better your estimate, the better the algorithm will be.

Let's take your situation as an example. Basically you'd get to a point where you might have something like this:

xxxxxxxFxxxxxxxx
x x
x xxxxx xxxxxxxxx
x o x
xxxxxxxxxxxxxxxx

Where x is a wall, F is the finish and o is the current enemy. A* knows that expanding to the left is useless in this scenario. You'd use a function that calculates the distance between two points (the location and the finish) and because the distance from the left point + distance travelled is greater than distance form the right point + distance travelled it chooses to expand to the right all the way to the end. It would find the perfect solution without expanding any extra nodes.

You might've read the section on increasing the speed of the algorithm, which has to do with dispraportionally weighting the distance you need to travel so that the algorithm wrongly expands nodes so that it analyzes less of them, but doesn't always get the right path. This is not required, and an even weighting won't do this, but if the algorithm is being slow, or you need to do it a lot and accuracy isn't 100% important than it's a useful tool.
Raknarg




PostPosted: Fri Jun 15, 2012 9:19 am   Post subject: RE:Pathfinding Algorithm

Ok, well when you explain it that way it makes more sense.
mirhagk




PostPosted: Fri Jun 15, 2012 12:28 pm   Post subject: RE:Pathfinding Algorithm

The picture came out retardly because I forgot about whitespace, it's supposed to look like this:

code:

xxxxxxxFxxxxxxxx
x              x
x xxxxx xxxxxxxx
x  o           x
xxxxxxxxxxxxxxxx
Raknarg




PostPosted: Fri Jun 15, 2012 1:57 pm   Post subject: RE:Pathfinding Algorithm

well, I just found out that on a completely open field, my algorithm can run 1500 times the exact same (seemingly) as it can run once, so I think I'm good for now Razz
mirhagk




PostPosted: Fri Jun 15, 2012 3:50 pm   Post subject: RE:Pathfinding Algorithm

yeah of course, just thought I'd mention it, it's an algorithm worth learning (can win you quite a few programming competitions)
Raknarg




PostPosted: Sat Jun 16, 2012 12:57 pm   Post subject: RE:Pathfinding Algorithm

Alright thanks
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 14 Posts ]
Jump to:   


Style:  
Search: