Would this be useful to any of you?

I know there are many of us programmers that rely on networks (of various things, like telephone exchanges, computers, etc) so this is relevent to some of you.
I am building an application that works out the Minimum Spanning Tree for a set of coordinate data (2 dimensional at present).

An MST is a little difficult to explain but here goes:

I own a group of islands, and I want to be able to get from any one of them to any other simply by walking. So I need to build bridges between the islands, fair enough. But wood is expensive here, so I will have to find the way of arranging the bridges that uses the least amount of wood.

The included screen shot is a finished MST of a group of 75 "islands" (the maximum number that this program can handle is 200).

The diagram will scale up to however large the form is at the time, including maximised. The full coordinate data and the diagram can be printed out. Full data about each "bridge" is included also.

So what do you think? Is this of any use to you engineers out there (I'll probably just give it away or free, since it was just an exercise in logic for me!)?

I'm still adding the finishing touches, should be completed in a week or two.

I'd be interested in taking a look at your code when you are done.

great man!
i need that for a game!

I'd be interested for flow control.

Is it flexible? Can user define each point?

Thanks for the response guys! :)

James - Yep, the user can specify any number of points between 3 and 200 inclusive. The coordinates of which can be mixed sign (above and below zero on both axes), the actual coordinate values are restricted to valid Single datatype values, but I am thinking of increasing this to Double if anyone thinks it is necessary.

I have chosen 200 points (or entities as I call them in the program) because of memory and speed of execution issues...

The number of potential 'bridges' follows this rule, where X is the number of entities:

PotentialBridges = (.5*(X*X))-(.5*X)

Therefore, if you have 200 entities, then you the program must make space in memory for 19,900 instances of the bridge datatype! Plus the execution time increases exponentially with a linear increase of entities, it would take days on my PC to do 500 entities, but 200 is done within 80 seconds.

I'll have a distributable set of source files ready in a couple of days and I'll post it up on here, so bookmark this URL for the next week or so :)

I admit that the code is not as fast as it could be, I have been pre-occupied with getting the recursive logic right. But I'll get down to some serious optimisation tomorrow and hopefully ditch a large collection object forever.

The method of loading the points in is still a little primitive, but it works just fine. Just a simple ascii text file with the coordinates in this format...

1.445255,13.559876,""

Where the third value is a string that lets you give each entity a name! Cool eh? I thought of that one last night, it all shows up on the print out in a nice orderly manner, more or less :)

Only the first 200 coords at most are loaded from a file, this value is defined in the module as a constant.

I have only had opportunity to calibrate the print out details to my own printer (Brother HL1030 fyi) but I have done it in as generic a way as I could for widespread compatibility.

Anyway if anyone has a file full of coordinates they want me to test in the mean time while I prepare the files are welcome to email them to me and I'll send you back the MST for it :)

Oh yeah, before I bore you all to sleep, the display of the finished article can be flipped along both the X and Y axes at whim and it will even print out in the chosen orientation.

Sounds tasty even if I say it myself!

Nearly there! The Collection has been done away with, leading to an increase in speed of about 10-15 percent.

I'll post the code tomorrow morning.

Here it is!

The program runs about twice as fast when it's compiled, I recommend this.

Use the 5 text files (from the Load menu item) to generate the diagrams and data.

Any and all comments are very welcome.

I downloaded it...

Suggestion : Allow user to change points dynamically at runtime...

Ie : Let user update the point values in the grid and refresh to point layout...

Like it alot. :)

Thanks dude!

Can't believe I left that feature out. Perhaps I was pleased to get it working at all!

I'll get right on it, any other ideas while we're here?

PS do the small menu icons (for the graph orientation) show up when you run it? I was having a few problems with that the other day. Should be sorted out in theory though.

yeah, they do show!
cool work, man!

What a relief!

I'm going to use a picture box to display the entities on screen instead of the form's client area. This will let me better organise the form's controls into a more conventional layout.

I'll try to get some sort of Drag/Drop system for editing rigged up too.

Hey, would any of you fancy collaborating on this? I think this has potential for grandness (dream on wossy!).

ps, thanks for the 5 star rating, whoever did it :)

Me! Me! T´was me! :D

No, really, man!
You´ve done great work!

They love me, they really love me!

I'd like to thank my producer, there he is in the third row, he's a joker!...

yada yada yada

heh heh :D

Oh yeah I forgot to ask, is it any good for your game? I could probably speed it up a bit here and there. What sort of game is it?

Well, I tried to use it for finding the shortest distance.
I´ll post the picture here, ... wait...

http://www.vbforums.com/attachment.php?s=&postid=638214

Ok, you can´t use the red line, so you need to calculate the green line with as many points as possible on the line.
Unfortunately, I don´t know how to use your code for that problem.

But I´m writing many progs. I think I also will need your code one or two times....
Óf course I´ll give you credit... :cool:

Maybe, if you tell me, how to use your code for my problem, I would be very thankful! :D

One idea has just sprung to my mind, I'm going to hijack your picture for this one...

The blue spots are at positions between a pair of your black ellipses, directly half way between them in fact. (although its only a hand drawn approximation on my part). The pink lines are there to show you which pair of ellipses the blue spots belong to, I suppose you could call the two ellipses "parents" to each blue spot.

Anyway, having the blue points in these positions means that you cannot possibly hit a black ellipse if you stick to the green path. You would have to delete all blue points that fall within any of the black ellipses.

Just a preliminary idea you understand but I think it's a good place to start.

What do you think?

One thing I have not yet catered for in my program is the facility to find the shortest route between any two of the points in the structure. Only adjacent ones are done, although indirectly.

I reckon this will require another recursive function to calculate. Please feel free to try this yourself, butcher my code to your hearts content. I have quite a lot on my plate with this, since I compiled a list of improvements last night and I havent started that yet!

Thanks for giving me a mention in your game (if you use it), very much appreciated ;)

What would you (and you James) think of a collaboration effort?

Man, you´re some kind of a genious! You freak! :D :D
That idea is great! But how do i know, to which point, i would have to go?
Anyhow, if it works, i´ll use it in the game
BTW: What is a collaboration effort? (I´m german, sorry) :rolleyes:

Your english is very good, I didn't guess you were from another country.

A collaboration is where two or more people work together on a project. For example if a book has two authors then they would be collaborating on it.

Not a genius :) not by a long way! I have a lot of books on the subject of pattern recognition and artificial intelligence, that kind of thinking rubs off after a while, it really is an utterly fascinating area of research, for me anyway.

I am not sure how to begin programming my idea yet, I sometimes wish I could connect my brain directly to my PC, it would save a lot of coding! heheh

I'll set aside some time to tackle this navigation problem today.

Thanks dude!
I love English :D It´s a great language, so I read the original English Version of most books (and I read at least one every two weeks) ;)

Well, if you need people to work with you, I´m your man! I´m interested in AI too, but don´t have any books on that topic. :(

My mail Adress is [email protected], if you wish to write me some mail!

Greets,
Alex

Cool, I'll make a note of it.

I'm at [email protected]

Are you interested James?

Here are a few books that I think are a good place to start researching AI...

* "Artificial Life" by Stan Franklin, a difficult read but once hooked, it is a stunning book.

* "The Blind Watchmaker" by Richard Dawkins, Easier to grasp than the first book, very interesting and hard to put down.

* "The Collapse of Chaos" - Penguin books, More mainstream than the above books, in less detail, but interesting and insightful.

* "Brief History of Time", Stephen Hawking. Not bad at all! Essential reading.

* "How to Build a Mind" by Igor Aleksander, Philosophical blockbuster.

I'm still building up my modest research collection, my number one most wanted is "The Art of Computer Programming" by Donald Knuth. Expensive, but no programmer should be without it.

For my Game i´m trying to make a bot. It shoud have some functions:

* Attack
* Idle
* Sleep
* Eat
* ...

Attacking should be based on your equipment and on his life.
I.E.: If he has 60life, a crap armor and only a mace, and he sees, you have a greatswors, full breastplate and whatelse, he will run away....
Are you interested?

Well, I'm used to creating more advanced AI but I suppose it would be interesting from a navigation / object avoidance perspective.

Sure why not :)

MORE advanced?
I didn´t list all of the purposes, the bot should should have....
It should, for example, try to speak with people, if they are friendly to him.

Look, the Bot should be some UserControl, because then you could set the values easier and make some array of them.
If you set - for example - the BotType Value to LWABOT_Friendly, it should no sooner attack you, than you attack him. If you speak with him, it´ll giva answers. (Standard Speech: "Hi!", "Hello!",.... and advanced speach. It should also react on a certain keyword by replying with a certain sentence...)
If you offend him, he will become angry. If you steal from him, he should become angry, if he´s too angry, he should attack you.
I don´t know, if you did that before, but it seems quite difficult.
It should also - if he´s following you, calculate the shortest distance from him to you every time you move....

Ok, that sounds more like proper AI :)

Will the bots learn that talking to friendly people causes them to prosper over bots that kill friendly people (for example), or is all the knowledge in-built at the beginning?

Will his aggression be proportional to the amount of 'life' he has left?

Everyone should have a random charakter, that changes, depending on how people treat him...
If a friendly one sees, you get attacked by an evil one, and the evil one is weaker, the friendly one should help you...

But i tried that often, it seems impossible to me...

Download and compile this newest revision. More than 4 times faster than previously!

I think it was the progressbar that was slowing down the algorithm. Goes like **** off a stick now though.

It be more streamlined enough to fit into your game now Ice, if we remove the GUI altogether then it should be blisteringly fast!

Do you have any code for your game? I'd love to have a look if you are willing to let me se it, I'd understand if you want to keep it a secret though. :)

Sorry, forgot to upload it with all the excitement!

wheres the atachment?......sounds great

o ok didnt c it you were posting when i was

WOW this is great

Thanks dude!

Check out the screenshot.

http://161.58.186.97/attachment.php?s=&postid=664150

I have added an info panel on the left and real-time '3 nearest neighbours" graphical aids (a bit like a HUD in a plane, but far more advanced of course! heh).

The faint grey lines indicate the 3 closest points to the mouse cursor, the blue circles are centred on those 3 points and have a radius of their distance from the mouse. This helps when adding new points by eye alone, and can be switched off.

Alas it's too buggy to post up here but if you guys are still interested in helping then drop me a line and I'll allocate some programming duties (cool stuff too, not dull GUI chores!) and send you a copy.

Are you guys still interested in this, because I have reduced the execution time for 200 points to less than 1 second! (on my old P200MMX).

I have done away with the circles because they were useless, but they did look good :)

Points can now be added and deleted at the user's whim, and the tree can be re-built at any time.

I'll be deleting this thread in a couple of days due to corporate interest (wahooo!), so if you are still keen, speak up now :) !

That program is simply great. But I do not see to what you can add that :) but I know it's hard to do, nice work.

Thanks :D

I am thinking up new bits to add to it all the time, the 3 major problems I have to face at the moment are loading the file (mostly finished), saving the edited files (not even started) and letting the user specify two of the points in the system that the computer then draws up a route between ("Computer, how do I get from A to Z?"...."User, you must follow this route: A, F, H, U, T, J, Y, I, Z"). I have been building up the guts to make a start on the last one for about 2 weeks, but I always manage to find something else that needs implementing more urgently! lol.

If I manage it by tomorrow I'll post the new code here.

I'm re-writing this algorithm in managed C++ as a console app. I'm going for speed rather than good looks this time round!

I'm curious. Could this be modified to find the shortest route that visits each point and returns to the starting point?

For example.
If you have points A, B, C, D, and E. What is the shortest route starting at A, visiting all points, and returning back to A.

I tried doing this a ways back, and found that it IS possible, but the time taken to calculate the result increases exponentially VERY FAST, so that it becomes useless to calculate anything over about 10 points (i forget the number exactly).

Not exactly, but it is a relevant question, have a browse through my other thread on this topic...

http://www.vbforums.com/showthread.p...40#post1580440

That discusses it further :)