Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

100 Neutral

About Kenster

  • Rank
  1. Kenster

    How's my logic? C#

    Eh. I am not good at explaining. Let me just ask this again, if anyone can help me with this, I think it could be a step in the right direction. Quote: Here is my code. I need advice on some things. If the person can see lets say 2000 units. How far should my Splitting go? 2000 Units? 2500 Units? Also, if I have 40000 Entities, what should I go as far as splitting? 10 per square? 20? 500? Should I not check for that at all and just split it into small squares?
  2. Kenster

    How's my logic? C#

    Sorry. I use the normal toAdd stuff. When an outside thread goes to add an object, it just adds it to a normal queue. Then the main thread says "are there any to add". Same for the moved. The minion threads move the players while whena move happens, Object.Moved = true. Then in the main thread, if true, remove from Quad, re-add then moved = false. So its all good there. But I still need a way to lower the amount of objects in the main loop. Objects should only be active when an Entity (Real player) is around. Trying to figure out the best way to keep them out of the loop until I really need to add them in.
  3. Kenster

    How's my logic? C#

    As stated before, I don't query results when I need them as that would be too much overload. I simply have 1 thread that goes through and tells who is around who and store it in a list. When I send a packet, I go through that list and send to each, only locking that. This way I never need to lock the main update thread.
  4. Kenster

    How's my logic? C#

    NOTE* It currently takes about 6000MS to go through them all and let them all know who knows who. So trying to get that down to like 1-2 seconds. Maybe changing the above requested numbers will help or maybe just switching to an Oct may help. [Edited by - Kenster on August 14, 2010 3:20:57 PM]
  5. Kenster

    How's my logic? C#

    I did some good so far but I think I have a few areas to do better on. First, one area has 14 levels (Z-Axis) and I think I need to move from a Quad to an Octree. As some collisions are 150+ units in one area. (Due to all being on top of each other). public class QuadTree { QuadTreeEntityNode root; public List<Entity> entities; public QuadTree(int width, int height, Point position) { root = new QuadTreeEntityNode(width, height, position); entities = new List<Entity>(); } public void Insert(Entity b) { entities.Add(b); root.Insert(b); } public List<Entity> GetCollidable(Entity b, bool moving) { List<Entity> col = new List<Entity>(); root.CollidableBalls(moving, ref col, b); return col; } public Entity Find(Point position) { return root.Find(position); } public void Remove(Entity ball) { root.RemoveBall(ball); entities.Remove(ball); } public List<Entity> GetAll() { return entities; } } public class QuadTreeEntityNode { static int MAXITEMS = 20; static int MINSIZE = 2048; QuadTreeEntityNode tl; QuadTreeEntityNode tr; QuadTreeEntityNode bl; QuadTreeEntityNode br; List<QuadTreeEntityNode> sections; List<Entity> balls; int width, height; Rectangle area; Point leftCorner; public bool isFull = false; public QuadTreeEntityNode(int width, int height, Point leftCorner) { tl = tr = bl = br = null; sections = new List<QuadTreeEntityNode>(); this.width = width; this.height = height; this.leftCorner = leftCorner; area = new Rectangle(leftCorner.X, leftCorner.Y, width, height); balls = new List<Entity>(); } public void Insert(Entity ball) { if (sections.Count == 0) { balls.Add(ball); isFull = (balls.Count > MAXITEMS); bool minSizeNotReached = (width > MINSIZE) || (height > MINSIZE); if (isFull && minSizeNotReached) { CreateChildNodes(); foreach (Entity b in balls) Distribute(b); balls.Clear(); } } else Distribute(ball); } private void Distribute(Entity b) { if (tl.area.IntersectsWith(b.Box)) tl.Insert(b); if (tr.area.IntersectsWith(b.Box)) tr.Insert(b); if (bl.area.IntersectsWith(b.Box)) bl.Insert(b); if (br.area.IntersectsWith(b.Box)) br.Insert(b); } public void CreateChildNodes() { int newWidth = width / 2; int newHeight = height / 2; Point newTopCorner = leftCorner; tl = new QuadTreeEntityNode(newWidth, newHeight, newTopCorner); sections.Add(tl); newTopCorner.X += newWidth; tr = new QuadTreeEntityNode(newWidth, newHeight, newTopCorner); sections.Add(tr); newTopCorner.Y += newHeight; br = new QuadTreeEntityNode(newWidth, newHeight, newTopCorner); sections.Add(br); newTopCorner.X -= newWidth; bl = new QuadTreeEntityNode(newWidth, newHeight, newTopCorner); sections.Add(bl); } public void Split(int x, int y) { if (sections.Count == 0) { if (area.Contains(x, y)) { CreateChildNodes(); foreach (Entity b in balls) Distribute(b); balls.Clear(); } } else { if (br.area.Contains(x, y)) br.Split(x, y); else if (bl.area.Contains(x, y)) bl.Split(x, y); else if (tl.area.Contains(x, y)) tl.Split(x, y); else if (tr.area.Contains(x, y)) tr.Split(x, y); } } public void CollidableBalls(bool moving, ref List<Entity> balls, Entity b) { if (this.balls.Count > 0) { for (int i = 0; i < this.balls.Count; i++) { if (!balls.Contains(this.balls)) { if (b != this.balls) { balls.Add(this.balls); } } } } if (sections.Count == 0) return; if (br.area.IntersectsWith(b.Box)) br.CollidableBalls(moving, ref balls, b); if (bl.area.IntersectsWith(b.Box)) bl.CollidableBalls(moving, ref balls, b); if (tl.area.IntersectsWith(b.Box)) tl.CollidableBalls(moving, ref balls,b); if (tr.area.IntersectsWith(b.Box)) tr.CollidableBalls(moving, ref balls, b); } public Entity Find(Point pos) { if (this.balls.Count > 0) { for (int i = 0; i < this.balls.Count; i++) { if (balls.Box.Contains(pos)) return balls; } return null; } if (sections.Count == 0) return null; if (br.area.Contains(pos)) return br.Find(pos); if (bl.area.Contains(pos)) return bl.Find(pos); if (tl.area.Contains(pos)) return tl.Find(pos); if (tr.area.Contains(pos)) return tr.Find(pos); return null; } public void RemoveBall(Entity b) { if (balls.Count > 0) { balls.Remove(b); // isFull = (balls.Count > MAXITEMS); //return; } if (sections.Count == 0) return; if (br.area.IntersectsWith(b.Box)) br.RemoveBall(b); if (bl.area.IntersectsWith(b.Box)) bl.RemoveBall(b); if (tl.area.IntersectsWith(b.Box)) tl.RemoveBall(b); if (tr.area.IntersectsWith(b.Box)) tr.RemoveBall(b); } public void GetBalls(ref List<Entity> balls) { if (this.balls.Count > 0) { for (int i = 0; i < this.balls.Count; i++) { this.balls.Moved = false; balls.Add(this.balls); } return; } else if (sections.Count == 0) return; br.GetBalls(ref balls); bl.GetBalls(ref balls); tl.GetBalls(ref balls); tr.GetBalls(ref balls); } } Here is my code. I need advice on some things. If the person can see lets say 2000 units. How far should my Splitting go? 2000 Units? 2500 Units? Also, if I have 40000 Entities, what should I go as far as splitting? 10 per square? 20? 500? Should I not check for that at all and just split it into small squares? Can anyone help me in converting into a Octree? Thanks all!
  6. Kenster

    How's my logic? C#

    Can anyone supply any links to tutorials or have any code they wouldn't mind sharing regarding your two types of suggestions. My current tests as of now are for about 40,000 objects and I can update in less than a millisecond. Ken
  7. Ok. So, I am working on an App that monitors the activity of objects in a large space. Object in the bottom left is no where close to the top right. But, we are talking about 20,000 or so objects. Here is how I planned on coding it. *Please understand everything is on multiple threads, so it must be thread safe*. As a object enters, it will put but into a main list of all objects in the world. That will cycle through each 100milseconds to determine if anything new needs to be added/or removed, then update each object. If the object has moved (determined by a bool) it will remove from the QuadTree and Re-add at its new location. It will then also get its objects in sight and push them into a KnownList that each object holds. Now stepping back. When a player log-ins they will be put into 1 of 4 or so threads that will also call and update. This update will, send packets to nearby objects, determine if it needs to be moved and set its location, it will update its health (basically all the logic). And lastly, it will take the information pushed from the main thread and process it. IE, If I already know about the object being pushed, skip. This makes the Quadtree not have be thread-safe and all the information can be put on multiple layers and not having to worry about locking anything. I would like to know if anyone was able to make a QuadTree that big with being thread-safe where each minion thread could call a GetList() and process on the spot instead of storing it in a queue. Any suggestions would be grateful, I have already searched all threads that come close to this. Thanks
  8. Hello everyone, over the course of years now, I have put some posts into here about my MMO. I have started from scratch with all my knowledge, and I have finally got something very stable running. My question comes here. Basically, I set up my world in a Grid. The Grid then parses between 8 threads (CPU Core # * 2) and then I run update() in those regions. Each region has a Queue of packets to send, and contains each Entity in game. Which is working great. The problem I forsee now is I want to keep the Database saving on its own thread. So really, it can max at 25% and I don't care. Either way, I can forsee myself having Threading issues here. I want to avoid locks because halting the Region Update could have some very harsh effects on proformence. I was thinking of a few things. A) Bool control ---- Basically just have IsSaving = true when it is, and the Update on that specific character will be skipped. Or even the reverse. If action is being made on that Character, then skip the Update. B) Have some type of locking. Again, I can see this being very poor. C) A queue for each Character. Basically, if a player wants an Item, we send a Delagte into the Queue. When its his turn from the Region to update, we run the Queue (Maybe even limit to ovoid over time in one Entity). We then can know simply if we can or cannot update if that Queue is being used. (If there is no Queue, there is no action for that player). I need some suggestions. I don't need any help on slowing down the updates or what to update when but any suggestions of communication between Character Data such as Items/Skills/Location would be nice. Any advice, or experience in the field would be wonders of help! Thanks all! Ken
  9. Working flawless! I love QuadTrees! I now query the amount of people around me and determine by that, how far I can see in front of me. I also slow down so that each run I only update 15 people instead of all at once, like the busy WoW town effect. 1) I do still have a CPU issue but this is because of the Garbage collector. Still trying to find some good documentation on what causes it, how to solve it. 2) Anyone have a suggestion for Broadcasts to the Knownlist? Example, I have everything in a ThreadSafeList. If I could find a way to broadcast without Locking, I could remove all locks and I really wouldn't need to lock anything. So, should I try to like do all the work without the thread, then do a CopyTo or something that I can broadcast the packets X to all players in Y list. (For example, sit, run/walk, move, talk in area, ect). My one friend suggested a pool allocator for byte[]s.
  10. Ok. So as stated before I have already preset regions. Now each region has its own Octree. My problem is ghosting the regions near it. When a play is on the edge of a zone line, we have an issue of having no data in that Octree because of it. How should I go about it? Should I ghost in all Entities within X reach of the entrance of the Octree or should I make the world one large Octree and process that way. I can see it be very easy to manage, but would I see a huge performance issue with processing 12000 Mobs, + 4000 Players in one Octree? Thanks, Ken **EDIT** OR! I had looked at a few peoples theory's such as Bigworld and what not. I could each region and its surrounding regions (8) are included as the QuadTree. So for example, if I was in E then ABCDFGHI would all have the same point in E's QuadTree. So, I would be able to limit the amount yet still see close regions. The problem I forsee here is, during my UpdateMove method, I will have to be worried about updating more than just 1 Quadtree, but 8 more to go with it.
  11. Quote:Original post by phear- So when's l2-paradise coming back? Lol. Eh? lol Yes. I have started using QuadTree. Of course this isn't a one day task but I already have it splitting the users between regions, but I have to work on the 2nd part that was stated about packets being sent via movement of the areas. Thanks all for the help, ill keep updated. Ken
  12. The lines are followed by the client. And I dont have the source to that anymore. As you speak of HashTables, I currently have all known entities in a List<> The problem is cycling through that list. I need to find the quickest way to either A) Go through the entire list, B) If the list is large, only do X amount. Problem with this is I have to ensure that the next time around, we do the rest. Personally, I think A is the way. But in what order is best.
  13. Sir, Sorry I didn't mention before, it is a 3D game. Basically, those grids I have are not just 1 set away. Since its a 3D game, I think your formula wouldn't work. The grids I stated could be as big as town. (I wouldn't say that big but they are not blocks). Its not like chess. So, when people get into the game, they go into a cell. That cell then is used when the update process goes through. When people move, if they are within range, they are added into the KnownList of the entity. Ken
  14. Quote:These algorithms can also be implemented extremely cheaply. You can even run the checks for updating this list every 100 ticks or something if you want to and cut the cost down so low that it becomes almost free. >_> This is probably what I am looking for. How can I run checks quickly? From my knowledge, I would have the cycle the entire List<> and check if a player has run to far from another player. Another problem could come into play is .Broadcasting() packets. For each person that knows of this person, broadcast. If the list is 400, that could be a large broadcast. Ken
  15. Some of what you mention have to do with the client. This is just server side. Simple. Its the MMO server. Players just need to know about other players near it. Some what you have mentioned I will look into, I have heard Trees is where I need to be, just never really worked with them. Ken
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!