Computer Science Canada Pathifinding |
| Author: | Raknarg [ Wed Jun 13, 2012 10:02 pm ] |
| Post subject: | Pathifinding |
I've been working on this for my class, and I decided to show it. Maybe someone can find this useful. All it basically does is find the shortest path from point a to b, and retraces its shortest steps from b to a. Also, if it finds b at one point, it never takes more than as many steps required for that path. It can shorten the processing times in some situations. It's just brute forcing mostly, so it's nothing special. I just like looking at it XD |
|
| Author: | Beastinonyou [ Mon Jun 18, 2012 11:42 am ] |
| Post subject: | Re: Pathifinding |
Interesting =P. I myself am looking into A* and how to apply it. If I can get A* working, I'd like to then try using Binary Heaps in it. It's all very intriguing; Good Tutorial: A* : http://www.policyalmanac.org/games/aStarTutorial.htm Even Better: Binary Heaps in A*: http://www.policyalmanac.org/games/binaryHeaps.htm A Path finding Module would be quite handy if it can be adapted well, and I'd assume would be a well sought-after module. My 2 cents =P |
|
| Author: | Raknarg [ Mon Jun 18, 2012 12:50 pm ] |
| Post subject: | RE:Pathifinding |
Interesting. Might be a fun summer project. |
|
| Author: | evildaddy911 [ Thu Jun 28, 2012 10:38 am ] | ||
| Post subject: | RE:Pathifinding | ||
ive been trying to get one working using A*, but i ran into a syntax problem: it wont let me use flexible arrays as a parameter:
any ideas on how to get around that? |
|||
| Author: | mirhagk [ Thu Jun 28, 2012 10:55 am ] |
| Post subject: | RE:Pathifinding |
You can pass arrays without knowing the upper bound in turing, it won't be flexible in the procedure though. |
|
| Author: | evildaddy911 [ Thu Jun 28, 2012 12:04 pm ] |
| Post subject: | RE:Pathifinding |
well the point of the flexible part was so i can resize it to the length of the path... i guess the only real way to do it is to make use a regular array, make it a function that returns the length of the path? |
|
| Author: | mirhagk [ Thu Jun 28, 2012 1:24 pm ] |
| Post subject: | RE:Pathifinding |
Well you might be able to implement your own flexible array, having it return a pointer, but yeah it's probably best to just use a regular array and return the length. |
|
| Author: | Raknarg [ Thu Jun 28, 2012 9:20 pm ] |
| Post subject: | RE:Pathifinding |
Actually, I would work with a linked list on this problem instead. That way you can keep track of all the branches. It's like a flexible web array, much better to work with seeing as it's not linear. Ever heard of those, evildaddy? |
|
| Author: | mirhagk [ Fri Jun 29, 2012 7:25 am ] |
| Post subject: | RE:Pathifinding |
I'd be scared to see how a linked list works in Turing lol. |
|
| Author: | evildaddy911 [ Sat Jun 30, 2012 9:12 am ] |
| Post subject: | Re: Pathifinding |
ive heard of linked lists, but i have no idea how to use them... i did the static array/return size, works pretty well, heres the result: the file also contains a randomize_map procedure, parameters are the map array, the width of the map, the height, the percent chance that a square will be open and an array of squares that need to be open and have an available path to all of them. |
|
| Author: | Raknarg [ Sat Jun 30, 2012 5:43 pm ] |
| Post subject: | Re: Pathifinding |
Actually, mirhagk, they are awesome as far as I can tell. I made a neat program with it, a self building 20 questions type game. Just make a text file to go with it calle 20Qs.txt like this: name of an animal nil nil It reads and writes the file. |
|
| Author: | chrisbrown [ Mon Jul 02, 2012 2:34 pm ] |
| Post subject: | Re: Pathifinding |
Raknarg, looks like you've implemented a binary tree which, though also awesome, is distinct from - and more complicated than - a linked list. While a tree node may have zero or more children, a list node may only have up to one. For this reason, a list does not contain any branches and so doesn't adopt the parent-child convention that trees use. Instead, the child pointer is typically called "next" (the next element) or "rest" (the rest of the list). The last node is usually empty but may point to the beginning of the list; this is called a circularly linked list. A list may be doubly-linked, where each node has a pointer to its parent, which you've done with your tree node. This is typically called "prev(ious)" and allows the list to be traversed backwards. If you remove one of the children from your node structure, you would have a doubly-linked list. You can see some visuals <a href="http://en.wikipedia.org/wiki/Linked_list#Basic_concepts_and_nomenclature">here.</a> |
|
| Author: | Raknarg [ Tue Jul 03, 2012 1:39 pm ] |
| Post subject: | RE:Pathifinding |
That was just an example of a linked list application. In the case of evildaddy, I'm fairly certain a tree like mine would be prudent. |
|
| Author: | Insectoid [ Tue Jul 03, 2012 4:57 pm ] |
| Post subject: | RE:Pathifinding |
No, that's an example of a data structure application. A linked list is a linked list, and a tree is a tree. A linked list is pretty much a unary tree. |
|
| Author: | Raknarg [ Wed Jul 04, 2012 11:37 am ] |
| Post subject: | RE:Pathifinding |
Look, that's jis ust a technical difference, the concept is the same thing, Are you telling me a tree is not a linked list? It is a list, that is linked in a tree-like fashion. If you understand any of the concepts, you'd be able to understand them all. I think it would be prudent to put them all under one name. |
|
| Author: | mirhagk [ Wed Jul 04, 2012 11:54 am ] |
| Post subject: | RE:Pathifinding |
A linked list is a very small subset of trees in theory. In implementation there are all sorts of optimizations you can make with a linked list that don't exist with trees. First of all not having an array, which halves the number of memory jumps you need to traverse the list, you can also optimize the traversal since there is only one next node. You can have doubly linked lists with only one pointer stored, which is a XOR of the previous one. There are even more aggressive optimizations you could make (such as having the last element point to a special function that stops the enumeration, rather than having if(pointer==0) checks the entire time) if you really wanted to with linked lists. The concepts are similar, but linked lists are for vastly different purposes than trees, and are a much simpler concept to learn than trees. |
|
| Author: | Dreadnought [ Wed Jul 04, 2012 12:05 pm ] |
| Post subject: | Re: Pathifinding |
Raknarg wrote: Are you telling me a tree is not a linked list? It is a list, that is linked in a tree-like fashion.
I have never seen a shopping list in binary tree form. I doubt anyone, even you, would consider that a list. A linked list is a group of node representing a sequence. Each node will contain data and a pointer to the following (and perhaps previous) node. The nodes are linked together by these pointers hence it is a linked list. A tree structure has a broader definition. A tree is a group of nodes each with 0 or more children and a single parent. Hence as was stated earlier, a linked list can be regarded as a unary tree. As you can see, this means that a linked list is also a tree, but a tree is not always a linked list. In particular, a binary tree is definitely not a linked list. If you must put them under a common name, trees and linked lists are examples of abstract data types. |
|
| Author: | Raknarg [ Thu Jul 05, 2012 4:14 pm ] |
| Post subject: | RE:Pathifinding |
Of course their purposes are different, but the concept is the same. That was my point. @Dreadnought thanks. And yes, I do consider that a list. Although I have difficulty explaining my own thinking... I'm probably being too abstract for myself. You're right. |
|
| Author: | Insectoid [ Thu Jul 05, 2012 4:23 pm ] |
| Post subject: | RE:Pathifinding |
Quote: Of course their purposes are different, but the concept is the same. That was my point.
A linked list is a tree, but a tree is not a linked list. The same way a square is a rectangle, but a rectangle is not always a square. |
|
| Author: | Raknarg [ Thu Jul 05, 2012 4:28 pm ] |
| Post subject: | RE:Pathifinding |
Yeah, I didn't say they were the same thing. A square and a rectangle are both quadrilaterals with similar properties. If you understand one shape, you will likely understand another although they are different. In fact, you might be able to understand a cube, although it is more complex, because they have similar properties, they can be considered the same thing, even though they are not. |
|
| Author: | Insectoid [ Thu Jul 05, 2012 6:29 pm ] |
| Post subject: | RE:Pathifinding |
Quote: That [your tree] was just an example of a linked list application. |
|
| Author: | mirhagk [ Thu Jul 05, 2012 8:02 pm ] |
| Post subject: | RE:Pathifinding |
@Raknarg it was more like giving some one a cube to teach them about squares. Sure the concepts are there, but it's overkill, and too much to take in at once. |
|
| Author: | Raknarg [ Fri Jul 06, 2012 10:14 pm ] |
| Post subject: | RE:Pathifinding |
It wasn't to be used as a method of teaching, it was an example of application. |
|