Posted: 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

Posted: 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;

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

Raknarg

Posted: Mon Jun 18, 2012 12:50 pm Post subject: RE:Pathifinding

Interesting. Might be a fun summer project.

evildaddy911

Posted: 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:

Turing:

type xy:
record
x,y:int endrecord procedure AStar (...var path: flexiblearray1..*of xy) *
*
* end AStar

gives me a syntax error
any ideas on how to get around that?

mirhagk

Posted: 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.

evildaddy911

Posted: 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?

mirhagk

Posted: 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.

Raknarg

Posted: 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?

Sponsor Sponsor

mirhagk

Posted: 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.

evildaddy911

Posted: 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.

Posted: 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:

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.

Posted: 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.

Insectoid

Posted: 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.

Raknarg

Posted: 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.