Path question

I am building a bookstore (Chamonix, 233, 33) that has seven rooms and is one floor in places, two or three in others and has a number of walkways in each room. I think it would be cool to have a virtual guide where if a visitor said take me to Archeology would be able to choose the correct path and lead the visitor to the Archeology section. But I don't know programming wise how to choose the correct path. Has anyone seen any resources on the web or have some thoughts about how to solve this kind of programming problem?

A very simple solution would be to create glowing path-lines in the floor/walls that lit up according to what they were trying to find. Preferably with an animated texture 'pulling' towards to relevant location. So you'd have multiple paths next to each other, all invisible, and one would light up when it's section was asked for.

A less prim-heavy solution would be to have one path connecting all locations, and program each prim to know whether or not it should light up if a relevant section was asked for.

Thanks for the reply Moleculor, but I think you missed what I was driving at. In real life I can look at the walkways through the build and see that to get from the Green room to the Pearl room I need to go north to the rose room, west to the orange room, and then up two floors. My question is how to get a program to figure out a short route between any two locations?

I think I have an idea that might work but would love to read up on this sort of problem if there is anything out there.

It's been a long time since my algorithms class, so I can't suggest a specific resource, but if you do a Google search on "pathfinding algorithms" you'll find plenty.

You may find that it's not worth the effort to implement a pathfinding algorithm, and that it might be simpler to show a visitor a map and let them find their own way.

Djikstra's algorithm.

Probably the simplest effective algorithm to do what you're looking for.

Why not have a programmed seat take the customer to the place depending on the chosen path? Similar to a Vehicle, but could as easily be a single or low prim cost?

Honestly, the shortest path between 2 distances is a teleport!
Just set teleports to each room, and people can find their way instantly. I would personally rather teleport to another section than follow a guide or some lights on the ground.

-Jason Foo-

Francis, thanks so much for the tip on Djikstra's algorithm. I'm no math whiz but I am beginning to understand thanks to some good interactive and other tutorials out there.



The thing is this bookstore is modeled after the real one I work at and the idea is to show people how to get around in the real store.

A simpler solution would be to have something like

list lWaypoints = [
<35.5, 64.6, 20.2>, "Dialetic Ontology",
<35.5, 70.2, 20.2>, "Archeology",
<40.0, 70.2, 20.2>, "Ethics",
...
];

Have a global variable that remembers where you are now (by name), a way for the user to tell you where they want to go, and a function that can get the indexes of these locations.

Then just go through the list, llSetPos'ing to each vector, wrapping around the end of the list if you hit it.

This is just the outline of a solution, and assumes that you can make one "grand tour" path, rather than a path that branches.

you've given me an idea for a library.

Idea: Have chairs in the library that would allow you to listen to audio books, news, historical speaches, etc.

How it works: Have the land benieth each chair parcled up so that one chair is on each section of land. Then have a different stream for each chair that would then connect to a shoutcast server. The chairs would send commands to the shoutcast stream source controling them through xml-rpc. To select and control the stream a HUD like what was used for Deus Via would be employed.

This plan would require server resources & land. This could be expensive to maintain.

Strife, In this case you could also just have mp3 files on a server and each parcel using a script to update the parcel URL, hence changing the song. Of course this way once the song is finished nothing will play until the user leaves the parcel and returns or the URL changes.

Then you run into the problem of possible copywrite violation inducement. It's best if they are streams. That way you can make sure only one copy is in use and provide reasonable* protection against theft. If it was done properly it coould be hosted by a RL library without legal worries (which would take care of the server requirements). Wonder if you could get a grant to do this?


*reasonable in this case just means it would be a minor bother to lift the works.

It would work well though for single-band showcase sites, where the selection is from their own material alone.

Quite a few independent bands are starting to get the hint now that contractual slavery to a label is no longer the only way of doing things.

A bunch of av's portraying the band while clicks from listeners queue up a playlist would be fun, and not costly as a band promotion. Only one of the avs would need land, the others could use basic lifetime accounts.

Internet streams nowadays legally have to pay for the songs they play. Or so it was about six-nine months ago. I don't know if the law has been overturned yet or not.

But that is for mass distribution where multiple people are all listening to the same stream. This would be setup so only one person could connect to a stream at a time and by doing so would "check out" (lock) the material while the stream was playing. Which should make it a library and not a steaming radio station (you can check out CD's at your local library so why can't this work?).

As to the legality of this setup i couldn't say. I'm not a lawer.

Anybody know where I can find a human-understandable description of this algorithm? Ie. one that doesn't require four years of post-secondary math schooling to understand?

Well... no. Djkistra's algorithm is a general purpose algo for finding a shortest path to visit all nodes in a graph of arbitrary complexity. This is a big important problem, but applying it to your dealie is like using a pile driver to crack a wallnut.

You have a small graph of limited complexity, you could figure out a good path by hand.

Well, I'm more curious for non-SL related applications, as I've been toying with writing a turn-based-strategy game, and pathfinding would be handy.

Of course, I don't know a whit about game programming, so I'm probably doomed from the start anyway, but...

For what it's worth, it computes the shortest path between two points in a graph of arbitrary complexity, not all points (ie. the traveling salesman problem)

Wed's right though, you could probably precompute a reasonable tour by hand. But it's just so much more elegant to find it algorithmically

Cross,

it's not that hard to get your head around It's pretty intuitive once you figure it out. I'm confident anyone with an idea of what a "directed graph" and a "priority queue" is will grasp it easily.

Yes that is the key. There are a bunch of web pages that explain it with all those math symbols I don't understand. Here is a page that describes it in plain english . Well mostly. Wherever you see the word 'cost' think of the distance between two points (aka nodes) or combined distances. Thanks again Francis for pointing me in the right direction. I'm going to start experimenting with it tonight.

I'm no guru of pathfinding algorithms but from what's been said so far, maybe you'd find the A* algorithm useful. There's an extremely nice article about it at...

http://www.policyalmanac.org/games/aStarTutorial.htm


I'm currently in the process of implementing this in LSL for finding a path from one sim to another. Going very well so far although it's can be very slow for long paths. Not really ready to release the code to anyone yet (still need to improve memory usage & speed) but track me down in world if you'd like to see it in action.

I don't believe the A* algorithm is a good choice in this case (due to the relative simplicity of the problem) nor in the sim-pathfinding case (due to the homogeneity of the graph).

The A* algorithm is actually a bit more complex than Dykstra, but can be more efficient, because it employs a heuristic.

IIRC, Dykstra is simple case of the A* algorithm, using a degenerate heuristic.

For my SL path-finding algorithm, I use a simple breadth-first search. It works pretty good

I used breadth-first, because, I only want to cross on a border, not a corner, due to SL glitchiness. That means all link weights are equal. So, the generality offered by Dykstra/A*/other pathfinding algorithms is otherwise useless.

edit: Trying to make english good-like

Whee, thank you all. I guess I've got a bit of math-heavy reading to look forward to!