Pathifinding

[Raknarg]

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

[Beastinonyou]

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

[Raknarg]

Interesting. Might be a fun summer project.

[evildaddy911]

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 end record procedure AStar (... var path: flexible array 1..* of xy) * * * end AStar

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

[mirhagk]

You can pass arrays without knowing the upper bound in turing, it won't be flexible in the procedure though.

[evildaddy911]

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]

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]

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?

[mirhagk]

I'd be scared to see how a linked list works in Turing lol.

[evildaddy911]

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.

[Raknarg]

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.

[chrisbrown]

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 here.

[Raknarg]

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]

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]

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.