Top Mud Sites Forum

Top Mud Sites Forum (http://www.topmudsites.com/forums/index.php)
-   Advanced MUD Concepts (http://www.topmudsites.com/forums/forumdisplay.php?f=7)
-   -   Can MUDs implement range/distance? (http://www.topmudsites.com/forums/showthread.php?t=18)

Alexei 07-10-2002 06:50 PM

TopMudSites.

wedsaz 07-10-2002 08:25 PM


Alexei 07-10-2002 09:53 PM

TopMudSites.

Sainos 07-10-2002 10:43 PM

I don't think a text-based game would ever get to the point where a GUI game can be as far as distance attacks. They're restricted to a certain number of directions, for one: most use the four cardinal directions, up, and down. There's no sense of speed in most codebases: ie, you move as fast as you type a direction. There are some well-done (::nudge TI::) implementations of character speed that make it very possible to play a fleet archer and outrun your opponents as you fill them full of projectiles. Other than these, though, the closing-on-the-archer concept is pretty hard to get away from, even when you extend range to greater than 1 room.

Automappers exist for some MUDs that show you the terrain of the area as you move, and creatures that exist near you. But this and character speed are just facets of what you enjoy about MMORPGs' range systems, and I'm of the opinion that duplicating it won't happen.

KaVir 07-11-2002 04:53 AM

The way we're handling this is that you can "target" any particular "thing" within your line of sight, and then move towards it, away from it, circle around it, etc. Thus in the case of a swordsman vs an archer, they would target each other and the swordsman would charge, while the archer retreated and fired. If the swordsman got too close the archer might instead target the nearby forest and start running as fast as he could.

wedsaz 07-11-2002 05:54 AM


thelenian 07-11-2002 07:37 AM

The only problem with pure coordinate-based systems is that in order to actually achieve results that are noticeably superior to a room-based system is that your coordinate resolution would have to be in the neighborhood of <1m. Anything less and effectively all you have is a bunch of rooms labeled by coordinates. You'll also have to implement 3d visualization algorithms in order to calculate what each person is able to see (You would actually have to use many of the same algorithms used in raytracing, just at much lower resolutions and minus the graphical rendering). Not only that, but everything you make will have to be modelled in 3d space. If not, it becomes impossible to accurately model line-of-sight (i.e. buildings will need to specify the locations of vertices in 3d space). In other words, it's a massive PITA, and will bring your host machine to its knees if you achieve anything resembling a respectable pbase. Also, rendering a 3d scene through a text-based interface is going to present some very difficult challenges. In room-based systems, the builder has complete control over the player's perspective. In a 3d system, the builder must design his/her areas with absolutely no knowledge whatsoever about the player's perspective. What does this mean? It means that you need seperate descs for every seperately identifiable aspect of an object, which must be modelled in 3d space. Let's look at what this might mean for a building:

Room-based system:

A large wooden shack, worn with age, sits here on the grassy knoll.

examining the shack might yield:
The old shack, its wood bleached grey by the ravages of time, leans to one side as if cowering from the elements. Faded yellow curtains are visible through two windows that seem to be gazing mournfully out onto the prarie.

looking at a window might show you the inside of the shack.

Coordinate-based system:

What you'd see would have to depend on where you are in relation to the shack. In order for that to happen, the builder must specify a different desc for each part of the shack, your visualization system would need to calculate what parts of the shack are visible from your perspective, and an AI system would need to determine what parts of what you can see are important enough that you should see on a toplevel cursory glance.

Closer inspection would tell the AI filter system that more information should be passed onto the viewer, such as more details about each visible object.

Looking at the window, you would have to calculate, based on the coordinates of the windows' vertices (which your builder did specify, right?), what the viewer can see from where he/she is located.

Building a passable description based on the parts of an object that are visible given the relative orientation of the viewer in MUD-style text format is a nontrivial task. Actually, it's far harder than doing graphical 3d visualization. Instead of employing relatively simple 3d->2d transformation algorithms and other well-documented procedures, you'll need to build an extremely powerful AI system that is able to interpret spatial data and produce a dynamically generated description that could pass for something written by a person. I may be mistaken, but I doubt that current AI technology is anywhere near being able to accomplish something like that.

Although the second case does indeed model RL more accurately, I prefer the first. The thing I like about MUDs is that much is left up to your imagination. Just enough information is provided to maintain suspension of disbelief, while letting your mind "render" all the parts that (current) technology will never be able to get quite right. One trend I've been seeing in many new MUDs is the attempt to migrate more and more of the experience from player imagination to hardcode. While understandable, as, in moderation, it provides the consistency and structure needed for a cohesive themed RP environment, this tendency, at least in my opinion, largely defeats the draw of a text-based game. I play MUDs because I'd rather leave most of the details to my own imagination. If I wanted realistic modelling of 3d space in realtime, I'd play a graphical MMORPG.

KaVir 07-11-2002 09:41 AM

When implementing eating and drinking in a mud, you don't have to develop a full simulation of the human digestion system. Equally, when creating a coordinate-based world you don't need to represent it with 100% accuracy - there is simply no need. All you need to do is create a close enough approximation, and most players won't even be able to tell. The additional overhead is fairly minimal (even if you're using a resource-intensive language such as LPC) and it can really add a great deal to the game. Most of us are creating games, after all, rather than simulations.

Here is a cut&paste from Nathan Yospe's "Physmud++" - it's a good example of how effective a coordinate-based system can be:

> look

The flat green plain stretches away into a distant ridge of hills to your right. Sixty meters to your left, a crop of trees springs up, thick and forbidingly twisted. The strange, flat grass crunches under your feet, releasing a pungent scent. Ahead, thirty meters off, a twisting blue stream makes its slow, twisting way out of the small dark forest. Sparse clouds drift by overhead. Something streaks by overhead with a roar. A cluster bomb explodes ten meters off ahead to your right! A piece of turf flies by, but misses you.

> run

You start running toward the stream.

> run forest

You turn toward the forest, running as fast as you can. A roaring sound reaches your ears. The forest is thirty meters away. Something roars by overhead, leaving the impression of a silver streak in your eyes. A whistling sound reaches your ears. An impulse makes you dodge left, and a reddish object streaks by your right ear. The missile starts to climb, but impacts into the forest. You keep running. The forest is ten meters away. You dodge as branch as you reach the edge of the forest. You stop, winded, to catch your breath. You are just within the edge of a small, gnarled forest. Ahead and to each side, crooked black branches tangle together, making it impossible to pass without considerable effort. Mushrooms grow out of the mulch and rot at your feet, and there is a damp smell to the air. The sun filters through the treetops, almost entirely gone by the time it reaches you.

> look plain

You turn around and stare out through the edge of the forest. The plain stretches out into the distance. Far ahead, the flat green plain stretches away into a distant ridge of hills. Thirty meters ahead and to the left, a twisting blue stream makes its slow, twisting way out of the small dark forest. Far off to the right, a fence surrounds a complex of buildings.

> hold rifle

You pull your plasma rifle out of the leather holster across your back and cradle it in your arms.

> reload rifle

The current bolt has a full charge. You don't need to reload.

> hold grenade

Shifting your plasma rifle into one hand, you detatch a sonic grenade from the strap across your chest and prime it. A pack of about twelve Logran drones is approaching from the direction of the complex of buildings. They are about 300 meters away.

> focus logran

You adjust your optical cybernetics to focus on the pack of Logran drones. There are fourteen of them. Magnification is at x300. The pack is led by a class three hunter. The Logran drones are carrying laser rods. The Logran hunter c3 is carrying a rail cannon. They are heading in your direction. They are about 250 meters away.

xotl 07-11-2002 04:34 PM

I implemented a system on Accursed Lands where each object in a room has an x,y,z coordinate.

Movement takes time, so the archer could easily shoot someone and slip away to the next room, finding a place to hide before the pursuer got there.

You also can't attack someone out of your weapon's attack range, ie: If they are flying far above you in the room, and you have a club.

Feel free to drop by and check it out, if you want to see one such text based system in effect.

Xotl

wedsaz 07-11-2002 06:02 PM

Well said KaVir, one can afford to be lazy when making a game. Room-based muds usually don't take these things into account, so why would a coordinate-based one have to do so?
.
Nice ad, xotl, but wouldn't it look better in the advertising for players forum?

Robbert 07-11-2002 07:14 PM


xotl 07-11-2002 08:12 PM


thelenian 07-11-2002 08:54 PM

Because that's the whole point of having a coordinate-based system--if you don't, you basically lose all the important functionality a coordinate-based system offers that can't be done in a room-based system. The rest of the functionality described here could more easily be implemented in either a room-based system, or a hybrid system. If all locations in your coordinate system are point objects, and do not have volume, all you've really done is masked a room-based system by replacing each room with a bunch of autogenerated rooms for each point on the grid.

wedsaz 07-11-2002 09:36 PM


thelenian 07-12-2002 12:48 AM

Ahh, yes, coordinate-based system for pure wilderness is much more feasible. You start to run into most of the problems designing the heuristics for an AI interpreter that does raw spatial data->human-readable text on man-made objects and environments.

As for mentioning the name of a specific MUD, it's generally considered bad form unless it's either:

A) absolutely necessary to make your point clear

or

B) explicitly asked for (as is the case when someone asks where they can see a working implementation of X)

wedsaz 07-12-2002 01:53 AM


thelenian 07-12-2002 02:19 AM

Pathfinding is incredibly trivial compared to the kind of interpretive AI I mentioned earlier.

I had on the subject (pathfinding) on TMC a while back.

KaVir 07-12-2002 07:46 AM

It can, yes - and I've done it in the past - but generally I found the results to be a bit disappointing compared to a true coordinate-based system, as the "rooms" still create artificial boundries which interfere with combat.

Try reading the post pinned to the top of this forum, entitled "Pinned: Posting Guidelines, IMPORTANT: Please read".

Icons and sigs are generic, so it doesn't really matter what you place in them, but each post is written individually - so (in order to try and keep a decent signal/noise ratio) I ask people not to post adverts in this forum.

Not so - even without giving things volume, you still gain a number of major advantages from the coordinate-based approach. In particular, you'd be able to calculate distances, allowing you to easily implement a decent ranged combat system (which was, after all, the subject of the original post).

It would also allow you some excellent opportunities for melee combat, including tactical positioning (eg attacking someone from behind), weapon lengths, and best of all a reasonable approach to fleeing from a fight. You wouldn't have to worry about someone typing "flee" and suddenly vanishing into another room, because you'd actually be able to SEE them running off - and give chase, if you so wished. Furthermore because the world is logically layed out, and you can see beyond the constraints of an artificial "room" entity, you'd be able to take short-cuts rather than having to follow their exact route.

In addition you'd be able to implement one of my favourite features, which is ranged sound. A "whisper" wouldn't be a private channel, but instead would be a very short-range channel. Equally a "shout" would travel a lot further, particularly if you were standing on a hill at the time. The "sneak" skill might allow you to move a lot quieter, but you'd still make SOME sound as you walked around - so a very perceptive person might hear you creeping up on them (or possibly even hear you draw your weapon). The sound of battle would also travel, and you might well hear the sound of steel striking steel as two people fight nearby. You could even spawn sounds as events, to realistically simulate sound moving slower than light - useful when trying to determine how far away the lightning is (personally I think that's going a bit OTT for most muds, but it would be fun to code).

cronel 07-12-2002 09:08 AM

Are there any published examples of a coordinate based system? Any codebase, or anything? I would love to see an actual implementation.
--cronel

KaVir 07-12-2002 09:32 AM

Telford's entry in the is coordinate based.

If you're interested in design approaches, you may want to search the , as this topic has been discussed extensively there.

07-16-2002 10:30 PM

Could you elaborate on your user interface?
How do you handle facing?  Or player motion?  
Can players be set in motion towards some landmark?

wedsaz 07-17-2002 12:40 AM


KaVir 07-17-2002 05:38 AM


Robbert 07-18-2002 08:52 PM

Add a 'head' command, allowing you to continue to move in a particular direction until you no longer can (or azimuth, such as head northeast or head 270 degrees).

I'd suggest, for intuitivity, that you have commands for the paces as well as a pace-setting command, so someone could do "run north" or "pace north" and then "run".

With our new engine, we are creating an analogous command interpreter - it will attempt to determine the command(s) you wish to do based on the construct of your sentence, rather than require you input your command in a specific format. One of the things this does is recognize the paces and change to them automatically. You may want to consider a similar approach, if you're not already.

Movement should be intricately linked with combat, in my opinion - all current paradigms restrict combat to the room or area in which it began, and this is not how it should be. Allow for the participants to set specifics about themselves (if the pressed, retreat or stand ground? If opponent retreats, do we press the advantage or hold back?), and then let combat meander as needed. If done properly, one could use objects and terrain in the area to ones advantage. I don't know if this is putting too much depth into it, but it would be great to fight in the dark and have your opponent trip over the caltrops you've strewn through the area.

With ranged combat, allow for misses to possibly strike others in the surrounding area. If someone passes through the trajectory of an object, perhaps it will hit them, or they will deflect it enough to where it misses its target.

KaVir 07-19-2002 06:26 AM


mhc 07-23-2002 02:25 PM


Robbert 07-23-2002 03:06 PM

Additionally, if you track locations of *thing relative to other *things in the area, little work is necessary to extrapolate the information for the player(s) - work recursively based on the closest thing to them, and continue until they can no longer see based on other things in the area.

(Edit) - This works for sound as well as sight, and the theory is the same. Working from a known reference otuward makes much more sense, in terms of intensity, than taking a mass of things and checking each one to see if it is visible/audible to the character. And it allows for neat additions such as poor eyesight or hearing, and their reverse. (/edit)

Our system of location is based upon inheritance; you can be literally be in a forest and see the trees, or move to a particular copse/meadow/field that has been created within it. This allows for the world creators to give as much or as little detail as necessary. So a City could be visible from the forest, but the individual buildings of it need not be apparent until one is outside a gate of that city, or within it itself.

Kastagaar 07-24-2002 04:25 AM

Surely the simple case would be to determine what distance is considered "near" and list all items that space, which is O(n).

Kas.

mhc 07-24-2002 09:26 AM

Only of you only have one player.

Loriel 07-24-2002 09:55 AM

If the problem is 'finding items near a specified player', I believe it is O(n) where n is number of items.

If the problem is 'finding items near each player' I believe it is O(p*n), where p is number of players and n is number of items.
In that sense, it might be roughly O(n*n) where n is number of players.

Finding players near each player would be O(n*n), where n is number of players.

Robbert 07-25-2002 01:27 PM


Loriel 07-25-2002 02:52 PM

I think I failed to make my point clear - I was supporting your (Robbert's) proposition that the basic algorithm would be O(n), before further improvements.

The only circumstance I can see where the O(n*n) would apply is the one I quote above, finding number of players near each player.

You could look at one 'game loop' in this context, where you might need to construct n 'player views', each of O(n) approx, so the complete game loop computation is O(n*n), though even in this case I think O(n*p) is a better value.

As you said, there are various improvements that would reduce this in practice.
For example, if we have found when constructing Frank's view that Frank is near Ruprecht, we know when constructing Ruprecht's view that Ruprecht is near Frank and don't need to calculate it again .
Similarly if Frank is near Ruprecht, and Ruprecht is near Wilhelmina, we know that Wilhelmina is at least 'fairly near' to Frank, though we may need to refine that.

Alexei 07-29-2002 01:32 PM

TopMudSites.

Raghar 08-04-2002 06:40 PM

Hello boys I'm doing some very hard and complex simulation and I found this topic very interesting. Basicaly I simplified seeking of targets to something like 3D room and I wanna know if there is better and FASTER way to do this. I do probably have two problems big list for seeking and considering of what data I would need.
Could you post some links?

It's strange I do RPG Strategy Simulation and I found lots of interesting problems here, and not on the graphical/ game servers. Probably becose I have similar problems like muds but for different reasons. At least most of them are different.

Hersir 06-27-2012 03:34 PM

Re: Can MUDs implement range/distance?
 
This game is a recent browser/C# remake of a MUD that had a coordinate system/text map, and a sandbox style (players make everything) back before anything else did in the 90s.


KaVir 06-27-2012 06:57 PM

Re: Can MUDs implement range/distance?
 
You necro'd a 10-year-old discussion thread so that you could post a random promotion, on a board that explicitly asks you not to post promotions?

And no, your game was not the first to implement those features.

Ghostcat 06-28-2012 11:54 PM

Re: Can MUDs implement range/distance?
 
At least he necro'd an interesting thread.

camlorn 06-29-2012 04:09 PM

Re: Can MUDs implement range/distance?
 
Ok, so a few thoughts on this.

Firstly, godwars2 does this. Go look at it for a good example which is running still.

Secondly, there's a harder, but less processor intensive way of finding near objects. I forget what this is called--I'm not smart enough to have come up with it--and a lot of 3d engines use it:

The world is a quadrant forming the first node of a tree.
Divide the world into some number of quadrants--9 works well--and make them the next set of nodes in the tree.
Keep dividing until you get to the desired resolution.

To find an object in the same area as a player, you simply walk up the tree to the desired resolution and get the list from that. You can do that by finding all leaf nodes below the desired resolutional node (new term!), or you can sacrifice memory and store each object in all nodes containing it...so, the world node gets all objects.

If someone can remember what this is called, it'd be a help--I'm bad at explaining it.

Also, you can divide up the world into "regions" or "maps" or what-have-you, making the two lists in the o(p*n) algorithm smaller--p is the limit in each map and n the number of objects in that map. Should help anyway.

Ide 06-29-2012 09:59 PM

Re: Can MUDs implement range/distance?
 
I'm guessing quad trees camlorn, but I think there use is more typically for representing very large worlds than line of sight calculations.

camlorn 06-30-2012 07:07 PM

Re: Can MUDs implement range/distance?
 
Heh, well, it doesn't much matter. I didn't realize this topic spanned two pages and was replying to the old part from however long ago. Only just now realized that this was necroed for a random promotion and that I wasn't reading the latest post.

Oopse.

I think oct-trees are what I was talking about--might also be called quad-trees, I really don't know.

swampdog 07-03-2012 01:51 AM

Re: Can MUDs implement range/distance?
 
Haha well since you bumped it, not only are trees a cool thing to learn but the math for co-ordinate grids is very simple. And even if you are finding paths or distances all the way across your 100x100 grid the math executes very quickly - this pseudocode finds the distance between any 2 points basically instantly and it doesn't matter how far apart the locations are:

return square((x2 - x1) ^ 2) + ((y2 - y1) ^ 2)

Where, x1 and y1 are the co-ordinates of your starting point and x2 and y2 are the co-ords of your ending point, and this applies to all handling of the grids. You can use (fast) elementary math to crunch the numbers, and then figure out what your grids are representing, which could be a projectile in flight (which you would then poll, updating the X, Y positions of all flying arrows on a regular basis), or the types of resources available at any X, Y point on a map.

KaVir 07-03-2012 05:01 AM

Re: Can MUDs implement range/distance?
 
That's not the problem though. The problem is that most muds are room-based, and even if they laid their rooms out on a grid, those rooms would still represent abstract containers that restrict sight, movement and combat. You couldn't simply display everything within hundreds of rooms, the spam would be horrific - you'd need to make some fundamental design changes.

You'd also need to define the dimensions of each room, because a "room" could represent anything from a vast clearing in a forest to a tiny closet in a house. And to calculate the distances between two creatures or objects, you'd also need to track their position within each room.

You need to make sure you don't try to calculate the square root of a negative number. This is my solution:

I wouldn't bother tracking individual arrows. You'd need to update a lot more frequently to do that, increasing the load on the processor (particularly when you're tracking tens or even hundreds of thousands of objects) - and it make archery very annoying, because you'd never hit a moving target.

swampdog 07-03-2012 10:50 AM

Re: Can MUDs implement range/distance?
 
Having this system in mind from the beginning is pretty much required. You can also think of the room as the player's "view", in addition to container. One method I have seen used is moving the room instead of the player, updating as needed based on location, and splitting off new rooms to carry other players or creatures when they seperate.

I mentioned the simple math because it becomes easier to do the above when you can use your co-ordinates to generate and retrieve information (like terrain type) using . Now you don't have to store that terrain type anywhere, you just have to call your noise function with the same arguments as you did initially (x, y, max range of types, and generally a randomized, saved seed for each new map) and you will always receive that terrain type back, as part of an overall map. I think the room space definition comes down to codebase and the actual gameplay you want to represent, which might be a global fantasy overmap or a galaxy of solar systems. It took me about a year to do the following, starting with gridding all the rooms and generating them at planet creation time and then moving to an on demand system:

1 50x50 and 3 100x100 planets running (how well this will work with more players is unknown (this example has about 15 players running around)) but just re-using some rooms that are not occupied is a memory saver compared to creating the actual rooms at each point:

From the player's point of view, he can walk/drive/fly around with only the room he is in. All his stuff is where he left it because the rooms persist when occupied, but when he treks between points of interest he's actually in the same room the entire time, updating the view as he goes.


Once he goes into space he's inside a solar system that handles all interactions (scanning, auto pilot, move to coord, docking, orbitting, firing) based on object co-ordinates and can hop out if he wants, floating around as the ship leaves him behind. So it's far from a complete 3d co-ordinate based MUD but based on the type of game you want I think the specs on that are going to vary wildly. Window line of sight, interior room position would be a big deal in a shooter or survival game but doesn't matter at all on a surface warfare game with orbital strikes and vehicles and vice versa.

Arrows were a bad example, I was thinking of bullets from an FPS - a more reasonable MUD/MOO example would be a boat or starship on a heading at a certain speed.

KaVir 07-03-2012 03:43 PM

Re: Can MUDs implement range/distance?
 
I've implement that approach in the past, but if you're building the system from the ground up and want to use accurate rather than abstract distances, then IMO you're better off dropping the concept of rooms entirely. They're an artificial constraint that isn't well suited to this style of mud.

I've used that approach too, it has both pros and cons (which is why I prefer a hybrid approach) but it doesn't make it any easier (or more difficult) to calculate distances.

camlorn 07-04-2012 09:59 AM

Re: Can MUDs implement range/distance?
 
Since we've opened this conversation again:

Firstly, swampdog, I so wish wayfar1444 was more blind-friendly--I'd come offer to do it, but I just started coding over on cotn, and probably wouldn't have the time.

KaVir, the square of a negative is always a positive; the addition of two positives is always positive; the Pythagorean theorem can never result in the square root of a negative number--at least, not if done correctly.

As for the abstraction of arrows/bullets. No mud is going to have an update time fast enough for the player to notice whether or not you're faking the math; in most cases, even with such an update time, it's not going to show. Much easier to fake it. Given a coordinate and a vector, it's easy enough to determine if someone/something is in a certain range and on that heading:

given coordinate (x,y), and vector (xh, yh), we've got enough to draw an imaginary right triangle, so you can do all sorts of useful things. I can show the math, but it's probably way easier to get it off wikipedia; I've never done it in coding, so mine might be slightly wrong. In short, though, you've got an angle for player output and a slope, and:
y=mx+b. If you have m and some point, the point is on the line if that equasion works for that point. There you go, faked arrow trajectory.

And just an idea I've been toying with: empire mud clone. All the cities etc are rooms, in fact all the locales are, but when you go into combat, you go to a separate battlefield with your party and the enemies--think console rpgs here--with targettable features at the four edges, such as bridges, that let you exit, hazards, and of corse targettable enemies. Basically, godwars2 and empire mud. My point being, there's no reason you can't mix both; exploration, at least in my opinion, is much more engaging when you have all the complex text-adventure-like things rooms allow, and combat is more engaging when you cclone KaVir. Heh, I'm not too sure why no one has yet.

dentin 07-04-2012 12:36 PM

Re: Can MUDs implement range/distance?
 
Camlorn: KaVir is way ahead of you here. I believe his point was that if you use integer math and have big distance differences (greater than above 46000 units), you can end up passing in a negative number to the square root function due to integer overflow. These kinds of integer overflow problems are a really common problem in signal processing, and I've seen it a ton over the last ten or so years. Integer overflow makes up a significant fraction of C programming code bugs.

FYI, when KaVir says something I don't understand, I've found it to be good policy to assume I've missed something important. His track record on posts like this is extremely good. He wouldn't write up a complicated function to calculate distance if he didn't have a good reason for it.

-dentin

Alter Aeon MUD

camlorn 07-04-2012 03:12 PM

Re: Can MUDs implement range/distance?
 
Heh. I know that, dentin, but I was so sure this time...

True, though, integer overflow == fun. I'd not use c for a mud, however, so idk. I suppose it greatly depends on what language you're using whether or not that function or something like it is needed--I know python can promote numbers to bigint and I'm almost certain c# and java throw exceptions.

But yeah, listen to KaVir. I forgot the integer overflow.

Anyone know how his function is actually fixing the problem, though? He appears to be converting to double, but I'm not sure what cThing->location is supposed to be.

For those using c, it may be worthwhile to go read about the gcc extensions--in particular, long long (which is standard, now, I think), and 128-bit integers (which is even bigger and may also be standard). If we assume the maximum value of long long to be some measurement in meters, it's aproximately 1949.8640344137174849557028971024 light-years, unless my math is failing again. Beware, these may have performance penalties.

There is also the option of writing your own distance class of some sort, but that probably deserves a whole new thread, if not an entire article, and there's probably tons of literature on that already, and it may/probably isn't worth your time.

I still advocate oct-trees, a bit--there's problems with the pythagorean theorem for larger worlds unless you split them somehow. The truth is, I don't think there's much more that can be said in this thread without a bunch of specifics and someone actually working on a project asking for help.

dentin 07-05-2012 03:35 PM

Re: Can MUDs implement range/distance?
 
Camlorn,

By casting the xdiff and ydiff to floating point, he gives them arbitrary range. If they start out as ints, the difference ends up floating point. If you square an int, it can overflow. If you square a double precision floating point number, it probably wont (and if you start from an int, its guaranteed not to.)

Adding the two squares, each of which is now guaranteed not to overflow, also doesn't produce an overflow. So the square root function always has a valid input.

-dentin

Alter Aeon MUD

camlorn 07-05-2012 06:15 PM

Re: Can MUDs implement range/distance?
 
I know that much, dentin--I just don't understand all of it, mainly because I can't see everything it calls.

Didn't know floats and doubles were precise enough for this--it was my understanding that by the time you got to the integer overflow range, you're relatively close to the point at which you start rapidly losing precision. I suppose, however, it's better than a crash or something from wierd negative distances. Clearly I don't fully understand floats--do you have any online stuff that does a good job of explaining it, and where you start losing precision?

I'm not going to go through KaVir's function line-by-line saying what I don't understand; that's what I'd have to do to answer the question of what I don't understand about it, probably. That said, I don't believe in black boxes, with all the negatives that implies, and won't admit to understanding until I understand pretty much every line inside and out.

dentin 07-06-2012 12:48 PM

Re: Can MUDs implement range/distance?
 
I understand your need for level of detail, but I'll leave that for KaVir if he feels it necessary. I can answer the float/double question though.

Single precision FP, which is the 'float' type in C, only has about 24 bits of precision even though it's a 32 bit number. The remaining 8 bits are the exponent, which means that it can take on values such as 1.5e16, even though the largest possible number that can fit in 32 bits is about 4e9.

Double precision FP, which is the 'double' type in C, has about 53 bits of precision, out of 64 bits total. The exponent on the 'double' type can be a lot bigger, so numbers like 1.5e60 are possible.

Wikipedia has a big article on the theoretical construction and design of floating point numbers in general; it might be worth reading that as well.

Since KaVir is using doubles here, he's got enough bits that he's probably not going to lose precision in any of the operations. But even if he used floats, the loss of precision would be 'close enough' for pretty much all meaningful situations. Remember that you can still add 1e-16 to 1e16 and get a result, even if the floating point representation lacks the precision needed. It just won't be perfectly accurate.

-dentin

Alter Aeon MUD


All times are GMT -4. The time now is 03:22 AM.

Powered by vBulletin® Version 3.6.7
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright Top Mud Sites.com 2022