Rendering grid-based rooms

 
Post new topic   Reply to topic    mudlab.org Forum Index -> Design
View previous topic :: View next topic  
Author Message
Zygfryd



Joined: 01 Jun 2005
Posts: 6
Location: Poznan, Poland

PostPosted: Wed Jun 01, 2005 10:21 pm    Post subject: Rendering grid-based rooms Reply with quote

Hello everyone, I'm new here and I have a typical "I've got an idea but need people to help me work out the details" problem.

Imagine that rooms are not atomic containers but are a grid of tiles representing steps. Please note, this is not the same as having atomic rooms placed on an area grid. The significant difference is, that an arbitrary number of tiles could be visible from the player's position. Occlusion algorithms are pretty straight-forward in such an environment (paricularily shadowcasting).

What troubles my mind though, is the rendering of positional information and inclusion of different levels of detail. For example, when are 10 orcs rendered as "10 orcs" and when as "a pack of orcs", or how can you have a spoon rendered as resting in between a plate and a candle. Are there any studies out there or even algorithms ready concentrated on these details?

Another issue is the representation of multi-tile objects. One solution would be to represent objects as grids of tiles themselves. For example a table could be a 4x2 grid turnable around with a 45 degrees quantum, but that'd surely be a pain to implement.

I am open for any ideas, thank you in advance.
Back to top
View user's profile Send private message
Author Message
Huri



Joined: 18 Jun 2005
Posts: 8

PostPosted: Sat Jun 18, 2005 2:36 am    Post subject: Re: Rendering grid-based rooms Reply with quote

Zygfryd wrote:

What troubles my mind though, is the rendering of positional information and inclusion of different levels of detail. For example, when are 10 orcs rendered as "10 orcs" and when as "a pack of orcs", or how can you have a spoon rendered as resting in between a plate and a candle. Are there any studies out there or even algorithms ready concentrated on these details?


The orcs should be pretty straight-forward, something like 3-6 = group, 7-14 = pack and so on. Obviously 'look orc' (or your equivalent) should reveal the real number. The spoon is trickier. What's to say the spoon is resting between the plate and the candle, and not the candle and plate resting on both sides of the spoon? Or, indeed, the candle and the spoon resting beside the plate. You will basically have to make a choice which item is most important.

A general advice would be to do a couple of hand-translations from data representation to rendered text, and then see if you can create a general algorithm that ends up with the same result. This shouldn't be too complicated, just a bit tedious. Wink
Back to top
View user's profile Send private message
Author Message
Teelf



Joined: 12 May 2005
Posts: 21
Location: Seattle, WA

PostPosted: Mon Jun 20, 2005 6:37 am    Post subject: Re: Rendering grid-based rooms Reply with quote

Zygfryd wrote:
Imagine that rooms are not atomic containers but are a grid of tiles representing steps. Please note, this is not the same as having atomic rooms placed on an area grid. The significant difference is, that an arbitrary number of tiles could be visible from the player's position. Occlusion algorithms are pretty straight-forward in such an environment (paricularily shadowcasting).

Spatially, it is the same as grided rooms just at a different scale. Of course, it is conceptually quite different and will have a completely different feel to it (which is probably what you care about).

Zygfryd wrote:

What troubles my mind though, is the rendering of positional information and inclusion of different levels of detail. For example, when are 10 orcs rendered as "10 orcs" and when as "a pack of orcs", or how can you have a spoon rendered as resting in between a plate and a candle. Are there any studies out there or even algorithms ready concentrated on these details?


This is definetly an underexplored area. All I have seen is this article over at Skotos. I do not know if they actually use that system. I feel that this problem of figuring out spatial relations must be similar to some area (probably quite disjoint) of computer science, and once found could be plundered of algorithms. I have not put a lot of effort into this yet, so maybe someone else has a better idea...?

Zygfryd wrote:

Another issue is the representation of multi-tile objects. One solution would be to represent objects as grids of tiles themselves. For example a table could be a 4x2 grid turnable around with a 45 degrees quantum, but that'd surely be a pain to implement.

How about representing them with some descriptive text?
Back to top
View user's profile Send private message Send e-mail Visit poster's website AIM Address
Author Message
GenneX



Joined: 21 Jun 2005
Posts: 1

PostPosted: Tue Jun 21, 2005 9:16 am    Post subject: Reply with quote

Good Day Everyone

I came across this thread and thought I'd give out my perspective on it, seeing that I am currently working on a grid-based world for SocketMud.

Zygfryd wrote:
Quote:

when are 10 orcs rendered as "10 orcs" and when as "a pack of orcs"

This is quite a hard scenario to pin down, but I would have to say that the best and most suitable would be to look at scenario in complete.

1) Are these orcs scattered about, or within a certain vacinity close to each other?
2) Are these orcs a grouped community or are they just floaters?
3) Are these orcs of same nature, maybe different types of orcs, or different alignment?

A) Let's say there are 10 orcs:
A-1) Are these orcs scattered about ? (Yes = A-1-Y) (No = A-1-N)
A-1-Y) You see a bunch of orcs scattered all around you.
A-1-N) Are these orcs a grouped community ? (Yes = A-2-Y) (No = A-2-N)
A-2-Y) You see a community of orcs.
A-2-N) Are these orcs of same nature ? (Yes = A-3-Y) (No = A-3-N)
A-3-Y) You see a group/pack of orcs.
A-3-N) You see a bunch of orcs of different nature.

Now as you see what I have done is set three scenario variables to check and then depending on the outcome of those I determine how to inform the player. Now what I would suggestion to determine the numbers is as follow:
1) a single orc
2) a pair of orcs
Three or more would be
A) Scattered = a bunch of orcs
B) Grouped Community = a community of orcs
C) Same Nature = a group/pack of orcs
D) Other = a bunch of orcs

I'd say this is much more dependant on choice rather than an algorithm.

Zygfryd wrote:
Quote:

how can you have a spoon rendered as resting in between a plate and a candle

Hmmm ... this took me some time to get a good solution but I'd have to say positioning by using coordination within the tile will be the best.

Ok let's assume that a certain sized grid is called a location. Now each location would consist of a certain amount of tiles, depending on the x and y size of the location. Now I am also presuming each tile is equal in length and width to all the other tiles. Let's work with tile 1,1.

Code:

-----
-o---
-----


Now the 'o' represents the table with it's contents upon it, so let's zoom in.

Code:

     --|--
    ---=---
    ---0---
     -----


Now the '|' represents the candle, '=' the spoon and '0' the plate.

Great so we have the layout's now to do the rendering. For this to work each tile would have to have it's own coordination as well, so let's presume the tile is 3mx3m in size so our coordination would range from 0 to 299 (1 to 300 if you wish) by 0 to 299. Now placing the candle upon coordination 0,149, the spoon on 10, 149 and the plate on 50, 149 we can use the players position to determine how to render the scenario.

Now it is human nature to alway look at the nearest object to him first then going further, or looking from left to right.

So let's say the player was at 0,0 and he faced the table he would see the spoon is between the candle and the plate, this would be the same for 0,1 and 0,2. Now looking at 2,0, 2,1 and 2,2 it will be just the reverse where it will be the spoon is between the plate and candle. Again with 1,0 and 1,2 the player would look at it differently where 1,0 would be the spoon is between the candle and plate and 1,2 the reversed of it.

Now seeing that we have the players position and position of the tile of the table and then the positions of each object on the tile of the table we should be able to determine which objects would be seen first and which last.

Sorry if I explain poorly, but if you understand this it will most definitely give you a better idea on how to go about.

So to sum it all up, see everything within your mud as an entity and each movable entity should be able to change from position, where all tiles should have a sub coordination for placement of moving entities.
Back to top
View user's profile Send private message
Author Message
Teelf



Joined: 12 May 2005
Posts: 21
Location: Seattle, WA

PostPosted: Tue Jun 21, 2005 6:14 pm    Post subject: Reply with quote

GenneX wrote:
1) Are these orcs scattered about, or within a certain vacinity close to each other?
2) Are these orcs a grouped community or are they just floaters?
3) Are these orcs of same nature, maybe different types of orcs, or different alignment?

A) Let's say there are 10 orcs:
A-1) Are these orcs scattered about ? (Yes = A-1-Y) (No = A-1-N)
A-1-Y) You see a bunch of orcs scattered all around you.
A-1-N) Are these orcs a grouped community ? (Yes = A-2-Y) (No = A-2-N)
A-2-Y) You see a community of orcs.
A-2-N) Are these orcs of same nature ? (Yes = A-3-Y) (No = A-3-N)
A-3-Y) You see a group/pack of orcs.
A-3-N) You see a bunch of orcs of different nature.


You skipped over the hard (and fun) part of this problem. How does the computer know the orcs are scattered about or not? How does the computer know if the orcs are scattered around the player? What the computer knows is there are 10 orcs with 10 positions. Each position is, for example, 2 integers. How does it get from 20 integers -> scattered/not scattered?

A clustering algorithm might work, but would have to be used in a way that doesn't kill CPU. That would be a good discussion, I think.

GenneX wrote:

Now as you see what I have done is set three scenario variables to check and then depending on the outcome of those I determine how to inform the player. Now what I would suggestion to determine the numbers is as follow:
1) a single orc
2) a pair of orcs
Three or more would be
A) Scattered = a bunch of orcs
B) Grouped Community = a community of orcs
C) Same Nature = a group/pack of orcs
D) Other = a bunch of orcs

I'd say this is much more dependant on choice rather than an algorithm.


But you need the algorithm to have a choice.

GenneX wrote:
Now it is human nature to alway look at the nearest object to him first then going further, or looking from left to right.

<snip>

Now seeing that we have the players position and position of the tile of the table and then the positions of each object on the tile of the table we should be able to determine which objects would be seen first and which last.


But ordering objects from closest to farthest and left to right is the meat of the problem. As the player moves around the table the relationships change. So you have to calculate this relationship everytime every player looks and for possible every object in thier vision. Binary Space Partition (BSP) trees can be used to order objects from closest to farthest in an efficient way, but I remember concluding BSP trees weren't quite the right answer for reasons I can't quite remember. It may have been due to the splitting of objects.

I have implemented some code that determines if objects are behind/left/front/right of a player that I can go into if anyone is interested. It is mostly just some trigonometry stuff. I haven't tried to do any object to object relations yet.
Back to top
View user's profile Send private message Send e-mail Visit poster's website AIM Address
Author Message
Zygfryd



Joined: 01 Jun 2005
Posts: 6
Location: Poznan, Poland

PostPosted: Fri Jun 24, 2005 10:51 pm    Post subject: Reply with quote

Teelf wrote:
This is definetly an underexplored area. All I have seen is this article over at Skotos.

I have seen that article before and I'm leaning towards implementing it instead of grids, because it fits the narrative character of MUDs very well. It does have a couple disadvantages though. Since measurable distance doesn't exist, you can't compute any space or time constraints. It doesn't allow "in between" relations. Most relations are purely descriptive ie. even if a relation specifies a direction (like "north of"), you don't have enough information to make a spatial layout. No visual or sonic occlusion. But an ugly hack here and there could surely make it usable. I wonder if the narrative expressiveness can make up for the lack of distance and size to the players.

Teelf wrote:
How about representing them with some descriptive text?

I'm not sure what you mean, most objects have descriptions. The point of giving objects actual size, are the spatial relations between objects and players. People can sit at different parts of the table and in different order. The pain of having multi-tile objects is movement, because collisions could occur between parts of objects, and occlusion because in theory, you'd need to describe each segment of an object accurately enough to render only the visible part. A simple example would be: "You can see a corner of a heavy table from behind a red curtain, which splits the room in two sections, for smokers and non-smokers."

GenneX wrote:
So to sum it all up, see everything within your mud as an entity and each movable entity should be able to change from position, where all tiles should have a sub coordination for placement of moving entities.

It's an interesting idea, it does complicate the point-of-view algorithms though because they'd need to be run for each composite object separately. At least the algorithm I thought about, shadowcasting, which walks all visible discrete tiles of the scene. Not to mention covering of a object at a lower level of nesting with an object at a deeper level could be quite impossible.

Teelf wrote:
I have implemented some code that determines if objects are behind/left/front/right of a player that I can go into if anyone is interested. It is mostly just some trigonometry stuff. I haven't tried to do any object to object relations yet.

I've had a simple prototype somewhere too, if you do experiment with object relations though, please let me know.
Back to top
View user's profile Send private message
Author Message
kelson76



Joined: 27 Jun 2005
Posts: 30

PostPosted: Mon Jun 27, 2005 12:19 am    Post subject: Reply with quote

Teelf wrote:

You skipped over the hard (and fun) part of this problem. How does the computer know the orcs are scattered about or not? How does the computer know if the orcs are scattered around the player? What the computer knows is there are 10 orcs with 10 positions. Each position is, for example, 2 integers. How does it get from 20 integers -> scattered/not scattered?

A clustering algorithm might work, but would have to be used in a way that doesn't kill CPU. That would be a good discussion, I think.




Actually, this is very easy. You look at the upper bound, the lower bound, the left and right bounds. This lets you know the size of the grid that is occupied. You can find the length and width, which provides the number of square grid units that encompass the occupied area. You then look at the number of orcs occuping the area. Divide the # of orcs by the number of square grid units , which will give you a density factor. Just determine your density thresholds and you are set.

- Kelson
Back to top
View user's profile Send private message AIM Address
Author Message
Teelf



Joined: 12 May 2005
Posts: 21
Location: Seattle, WA

PostPosted: Tue Jun 28, 2005 6:29 am    Post subject: Reply with quote

kelson76 wrote:
Teelf wrote:

You skipped over the hard (and fun) part of this problem. How does the computer know the orcs are scattered about or not? How does the computer know if the orcs are scattered around the player? What the computer knows is there are 10 orcs with 10 positions. Each position is, for example, 2 integers. How does it get from 20 integers -> scattered/not scattered?

A clustering algorithm might work, but would have to be used in a way that doesn't kill CPU. That would be a good discussion, I think.




Actually, this is very easy. You look at the upper bound, the lower bound, the left and right bounds. This lets you know the size of the grid that is occupied. You can find the length and width, which provides the number of square grid units that encompass the occupied area. You then look at the number of orcs occuping the area. Divide the # of orcs by the number of square grid units , which will give you a density factor. Just determine your density thresholds and you are set.


That would be easy... if you had those bounds. Where do they come from? Also, it's not just about finding an algorithm. It has to be scalable.
Back to top
View user's profile Send private message Send e-mail Visit poster's website AIM Address
Author Message
Aioros



Joined: 16 Jun 2005
Posts: 14
Location: Lisboa, Portugal

PostPosted: Tue Jun 28, 2005 7:18 am    Post subject: Reply with quote

I may be wrong, but I think the bounds he was talking about are defined by the field of view of the character, usualy a circle or square for this kind of world implementation. The character has a certain distance he can look at, from there, the bounds are easy to get. It gets a bit more complicated when you implement collision detection to hide objects/mobs behind other objects/mobs, but it's still doable.
Back to top
View user's profile Send private message
Author Message
kelson76



Joined: 27 Jun 2005
Posts: 30

PostPosted: Tue Jun 28, 2005 2:35 pm    Post subject: Positioning.... Reply with quote

Teelf wrote:
kelson76 wrote:
Teelf wrote:

You skipped over the hard (and fun) part of this problem. How does the computer know the orcs are scattered about or not? How does the computer know if the orcs are scattered around the player? What the computer knows is there are 10 orcs with 10 positions. Each position is, for example, 2 integers. How does it get from 20 integers -> scattered/not scattered?

A clustering algorithm might work, but would have to be used in a way that doesn't kill CPU. That would be a good discussion, I think.




Actually, this is very easy. You look at the upper bound, the lower bound, the left and right bounds. This lets you know the size of the grid that is occupied. You can find the length and width, which provides the number of square grid units that encompass the occupied area. You then look at the number of orcs occuping the area. Divide the # of orcs by the number of square grid units , which will give you a density factor. Just determine your density thresholds and you are set.


That would be easy... if you had those bounds. Where do they come from? Also, it's not just about finding an algorithm. It has to be scalable.


If you are concerned about density of mobs in a room, you are working on a coordinate system of some sort. Hence you do a (max,min) function on the vertical and horizontal coordinates, which leaves you with the 4 numbers you need to grab the 'area' that encompasses the group.

-Kelson
Back to top
View user's profile Send private message AIM Address
Author Message
Teelf



Joined: 12 May 2005
Posts: 21
Location: Seattle, WA

PostPosted: Wed Jun 29, 2005 1:27 am    Post subject: Re: Positioning.... Reply with quote

kelson76 wrote:
If you are concerned about density of mobs in a room, you are working on a coordinate system of some sort. Hence you do a (max,min) function on the vertical and horizontal coordinates, which leaves you with the 4 numbers you need to grab the 'area' that encompasses the group.

-Kelson


Except, in this situation, a player's vision is no longer bounded by a 'room'. The OP said a room is a container of tiles (coordinates, basically) and there can be an arbitrary amount of tiles in what a player can see. So there are no bounds in the room sense. And your solution wouldn't work for situations in which there was say, two distinct groups of orcs.

I'd look into clustering algorithms for something that might be useful.
Back to top
View user's profile Send private message Send e-mail Visit poster's website AIM Address
Author Message
Huri



Joined: 18 Jun 2005
Posts: 8

PostPosted: Wed Jun 29, 2005 3:50 pm    Post subject: Reply with quote

For the "orc-clustering problem", one solution might be to go at it from another direction. What's making the orcs stand close together? AI, in which case there will be a defined group the individual orcs belong to and will try to stick close to? Are the orcs random-generated? In that case you might as well generate a group of orcs. Are the orcs placed there by a builder? Making him/her create a group of orcs instead of just placing individual orcs might be more convenient.
Back to top
View user's profile Send private message
Author Message
Ashon



Joined: 11 May 2005
Posts: 86
Location: Seattle

PostPosted: Sun Jul 03, 2005 8:35 am    Post subject: Reply with quote

Zygfryd wrote:
Teelf wrote:
This is definetly an underexplored area. All I have seen is this article over at Skotos.

I have seen that article before and I'm leaning towards implementing it instead of grids, because it fits the narrative character of MUDs very well. It does have a couple disadvantages though. Since measurable distance doesn't exist, you can't compute any space or time constraints. It doesn't allow "in between" relations. Most relations are purely descriptive ie. even if a relation specifies a direction (like "north of"), you don't have enough information to make a spatial layout. No visual or sonic occlusion. But an ugly hack here and there could surely make it usable. I wonder if the narrative expressiveness can make up for the lack of distance and size to the players.


IF you did add NESW directions to the Proximity chain you could definitely handle the 'in-between'. Of course, it depends on your implementation of the proximity chain. If you really wanted to get this indepth without changing over to a Coordinate system as even players move from room they join/break proximity, and you make it more as a proximity web, then a chain. And of course you run into a sorting algorithm, where you have to sort out the chain, and are probably better off going with a coordinate system.

A simpler hack would be to add a behind or in-front of moniker to the prox system. And it would fit within the reasoning of the standard room description where the spatial relationship is just kind of assumed by the reader.
Back to top
View user's profile Send private message Send e-mail Visit poster's website AIM Address Yahoo Messenger MSN Messenger
Author Message
ChristopherA



Joined: 22 Nov 2005
Posts: 2
Location: Skotos Tech, Berkeley, CA USA

PostPosted: Tue Nov 22, 2005 9:13 pm    Post subject: Re: Rendering grid-based rooms Reply with quote

Zygfryd wrote:

This is definetly an underexplored area. All I have seen is this article over at Skotos. I do not know if they actually use that system.


We do use the proximity system quite extensivly at Skotos, however, it is really for objects within the room itself. For instance when you first arrive in a room you are "near" where you enter. So if someone looked at you they would see in the look for the room "John is standing near the back door." As you interact with things, your proximity will change "John is standing near the bar". Your stance can change "John is sitting near the bar" or your proximity can change "John is sitting close to Julie. Julie is sitting near the bar."

It also affects consent, so if you are "close" to someone you don't need consent to hit them (provided that the game requires consent, not all do).

In the five years or so since it was implemented the proximity system has turned out to be one of our best features.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    mudlab.org Forum Index -> Design All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2002 phpBB Group
BBTech Template by © 2003-04 MDesign