为最短路径优化由 WPF 中的单元格组成的网格

Question

我目前正尝试在 WPF 中制作一个由 Cell 对象组成的网格。我需要将单元格绑定到需要在二维数组中的对象。 - 我需要它很大，可扩展并改变单元格的颜色并在对象中存储数据！

我做了一个实现，但是画格子好像很慢！（100x100 网格需要 >10 秒！）这是我已经制作的图片：

我在 ItemsControl 的 XAML 中使用数据绑定。这是我的 XAML:

<ItemsControl x:Name="GridArea" ItemsSource="{Binding Cellz}" Grid.Column="1" BorderBrush="Black" BorderThickness="0.1">
        <ItemsControl.Resources>
            <DataTemplate DataType="{x:Type local:Cell}">
                <Border BorderBrush="Black" BorderThickness="0.1">
                    <Grid Background="{Binding CellColor}">
                        <i:Interaction.Triggers>
                            <i:EventTrigger EventName="MouseMove" >
                                <ei:CallMethodAction TargetObject="{Binding}" MethodName="MouseHoveredOver"/>
                            </i:EventTrigger>
                        </i:Interaction.Triggers>
                    </Grid>
                </Border>

            </DataTemplate>
        </ItemsControl.Resources>
        <ItemsControl.ItemsPanel>
            <ItemsPanelTemplate>
                <UniformGrid Rows="{Binding Rows}" Columns="{Binding Columns}" MouseDown="WrapPanelMouseDown" MouseUp="WrapPanelMouseUp" MouseLeave="WrapPanelMouseLeave" >
                    <!--<UniformGrid.Background>
                        <ImageBrush/>
                    </UniformGrid.Background>-->
                </UniformGrid>
            </ItemsPanelTemplate>
        </ItemsControl.ItemsPanel>
    </ItemsControl>

在我的代码隐藏中，我实例化了一个名为 Grid 的 class 对象，它使用 Cell class 的对象创建一个二维数组（和一个列表，这是我绑定的对象）。在用秒表检查了一番之后，我发现这并没有花时间。它实际绑定和绘制网格，所以我想我的优化应该在我的 XAML 中进行，如果有任何优化可用的话。

但为了提供一切，这里是我的代码以及网格 class 和单元格 class:

    public MainWindow()
    {
        InitializeComponent();  

        NewGrid = new Grid(75, 75);
        DataContext = NewGrid;

    }

    public class Grid
    {
    public int Columns { get; set; }
    public int Rows { get; set; }

    public ObservableCollection<Cell> Cellz {get;set;}

    public Cell[,] CellArray { get; set; }

    public Grid(int columns, int rows)
    {
        Columns = columns;
        Rows = rows;

        Cellz = new ObservableCollection<Cell>();
        CellArray = new Cell[Rows,Columns];
        InitializeGrid();

    }

    public void InitializeGrid()
    {
        Color col = Colors.Transparent;
        SolidColorBrush Trans = new SolidColorBrush(col);
        for (int i = 0; i < Rows; i++)
        {
            for (int j = 0; j < Columns; j++)
            {
                var brandNewCell = new Cell(i, j) { CellColor = Trans};
                Cellz.Add(brandNewCell);
                CellArray[i, j] = brandNewCell;
            }
        }
    }

    public class Cell : INotifyPropertyChanged
    {
        public int x, y;   // x,y location
        public Boolean IsWall { get; set; }

        private SolidColorBrush _cellcolor;
        public SolidColorBrush CellColor
        {
            get { return _cellcolor; }
            set
            {
                _cellcolor = value;
                OnPropertyChanged();
            }
        }
        public Cell(int tempX, int tempY)
        {
            x = tempX;
            y = tempY;
        }


        public bool IsWalkable(Object unused)
        {
            return !IsWall;
        }
    public event PropertyChangedEventHandler PropertyChanged;

        private void OnPropertyChanged(
            [CallerMemberName] string caller = "")
        {
            if (PropertyChanged != null)
        {
            PropertyChanged(this, new PropertyChangedEventArgs(caller));
        }
    }
}

我喜欢带有绑定的非常简单的实现，但是加载时间真的不可接受 - 任何建议将不胜感激！

Answer 1

好吧，我重新创建了您的示例，但做了一些更改。我主要摆脱了 DataContext 上的绑定，并专门为您的用例创建了一个视图模型，它直接绑定到 itemscontrol。

画图的速度肯定在10秒以内，不过我想我给了你尽可能多的相关代码，所以你可以比较解决方案...

using System;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.ComponentModel;
using TestSO.model;

namespace TestSO.viewmodel
{
    public class ScreenViewModel : INotifyPropertyChanged, IDisposable
    {
        public event PropertyChangedEventHandler PropertyChanged;

        private IList<Cell> cells;
        public IList<Cell> Cells
        {
            get
            {
                return cells;
            }
            set
            {
                if (object.Equals(cells, value))
                {
                    return;
                }
                UnregisterSource(cells);
                cells = value;
                RegisterSource(cells);
                RaisePropertyChanged("Cells");
            }
        }

        private int rows;
        public int Rows
        {
            get
            {
                return rows;
            }
            set
            {
                if (rows == value)
                {
                    return;
                }
                rows = value;
                RaisePropertyChanged("Rows");
            }
        }

        private int columns;
        public int Columns
        {
            get
            {
                return columns;
            }
            set
            {
                if (columns == value)
                {
                    return;
                }
                columns = value;
                RaisePropertyChanged("Columns");
            }
        }

        private Cell[,] array;
        public Cell[,] Array
        {
            get
            {
                return array;
            }
            protected set
            {
                array = value;
            }
        }

        protected void RaisePropertyChanged(string propertyName)
        {
            var local = PropertyChanged;
            if (local != null)
            {
                App.Current.Dispatcher.BeginInvoke(local, this, new PropertyChangedEventArgs(propertyName));
            }
        }

        protected void RegisterSource(IList<Cell> collection)
        {
            if (collection == null)
            {
                return;
            }
            var colc = collection as INotifyCollectionChanged;
            if (colc != null)
            {
                colc.CollectionChanged += OnCellCollectionChanged;
            }
            OnCellCollectionChanged(collection, new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Replace, collection, null));
        }

        protected virtual void OnCellCollectionChanged(object sender, NotifyCollectionChangedEventArgs e)
        {
            if (e.Action == NotifyCollectionChangedAction.Reset)
            {
                Array = null;
            }
            if (e.OldItems != null)
            {
                foreach (var item in e.OldItems)
                {
                    var cell = item as Cell;
                    if (cell == null)
                    {
                        continue;
                    }
                    if (Array == null)
                    {
                        continue;
                    }
                    Array[cell.X, cell.Y] = null;
                }
            }
            if (e.NewItems != null)
            {
                if (Array == null)
                {
                    Array = new Cell[Rows, Columns];
                }
                foreach (var item in e.NewItems)
                {
                    var cell = item as Cell;
                    if (cell == null)
                    {
                        continue;
                    }
                    if (Array == null)
                    {
                        continue;
                    }
                    Array[cell.X, cell.Y] = cell;
                }
            }
        }

        protected void UnregisterSource(IList<Cell> collection)
        {
            if (collection == null)
            {
                return;
            }
            var colc = collection as INotifyCollectionChanged;
            if (colc != null)
            {
                colc.CollectionChanged -= OnCellCollectionChanged;
            }
            OnCellCollectionChanged(collection, new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Reset));
        }

        public ScreenViewModel()
        {
        }

        public ScreenViewModel(int row, int col)
            : this()
        {
            this.Rows = row;
            this.Columns = col;
        }

        bool isDisposed = false;
        private void Dispose(bool disposing)
        {
            if (disposing)
            {
                if (isDisposed)
                {
                    return;
                }
                isDisposed = true;
                Cells = null;
            }
        }

        public void Dispose()
        {
            Dispose(true);
        }
    }
}

我额外创建了一个控制器，它是 ObservableCollection 的所有者，主要目的是不对 viewModel 做任何更改，而是更改控制器内的集合（或添加、删除），清除它的方法），让事件链为我完成工作，使 ScreenViewModel

中的 2Dimensional Array 保持最新

using System.Collections.Generic;
using System.Collections.ObjectModel;
using TestSO.model;

namespace TestSO.controller
{
    public class GenericController<T>
    {
        private readonly IList<T> collection = new ObservableCollection<T>();
        public IList<T> Collection
        {
            get
            {
                return collection;
            }
        }

        public GenericController()
        {
        }
    }

    public class CellGridController : GenericController<Cell>
    {
        public CellGridController()
        {
        }
    }
}

还有你的单元格 class，我稍微调整了一下，只引发更改事件，以防万一确实有更改

using System.ComponentModel;
using System.Windows;
using System.Windows.Media;

namespace TestSO.model
{
    public class Cell : INotifyPropertyChanged
    {
        public event PropertyChangedEventHandler PropertyChanged;

        protected virtual void RaisePropertyChanged(string propertyName)
        {
            var local = PropertyChanged;
            if (local != null)
            {
                Application.Current.Dispatcher.BeginInvoke(local, this, new PropertyChangedEventArgs(propertyName));
            }
        }

        private int x;
        public int X
        {
            get
            {
                return x;
            }
            set
            {
                if (x == value)
                {
                    return;
                }
                x = value;
                RaisePropertyChanged("X");
            }
        }

        private int y;
        public int Y
        {
            get
            {
                return y;
            }
            set
            {
                if (y == value)
                {
                    return;
                }
                y = value;
                RaisePropertyChanged("Y");
            }
        }

        private bool isWall;
        public bool IsWall
        {
            get
            {
                return isWall;
            }
            set
            {
                if (isWall == value)
                {
                    return;
                }
                isWall = value;
                RaisePropertyChanged("IsWall");
            }
        }

        private SolidColorBrush _cellColor;
        public SolidColorBrush CellColor
        {
            get
            {
                // either return the _cellColor, or say that it is transparent
                return _cellColor ?? Brushes.Transparent;
            }
            set
            {
                if (SolidColorBrush.Equals(_cellColor, value))
                {
                    return;
                }
                _cellColor = value;
                RaisePropertyChanged("CellColor");
            }
        }

        public Cell()
        {
        }

        public Cell(int x, int y)
            : this()
        {
            this.X = x;
            this.Y = y;
        }
    }
}

然后我稍微改变了xaml（虽然没有接管交互点），通过为 ScreenViewModel、控制器和 DataTemplate 创建资源，这个模板，然后也是 DataTemplate通过 ItemTemplate 直接添加到 ItemsControl，而不是使用 DataTemplate 功能（没有将其视为上面的要求？）

<Window x:Class="TestSO.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:model="clr-namespace:TestSO.model"
        xmlns:viewmodel="clr-namespace:TestSO.viewmodel"
        xmlns:controller="clr-namespace:TestSO.controller"
        Title="MainWindow" Height="350" Width="525">
    <Window.Resources>
        <controller:CellGridController x:Key="CellController" />
        <viewmodel:ScreenViewModel x:Key="GridViewModel" Rows="75" Columns="75" />
        <DataTemplate x:Key="CellTemplate">
            <Border BorderBrush="Black" BorderThickness="0.5">
                <Grid Background="{Binding CellColor}">
                </Grid>
            </Border>
        </DataTemplate>
    </Window.Resources>
    <Grid>
        <ItemsControl ItemsSource="{Binding Cells,Source={StaticResource GridViewModel}}" BorderBrush="Black" BorderThickness="0.1" ItemTemplate="{StaticResource CellTemplate}">
            <ItemsControl.ItemsPanel>
                <ItemsPanelTemplate>
                    <UniformGrid
                        Rows="{Binding Rows,Source={StaticResource GridViewModel}}" 
                        Columns="{Binding Columns,Source={StaticResource GridViewModel}}" />
                </ItemsPanelTemplate>
            </ItemsControl.ItemsPanel>
        </ItemsControl>
    </Grid>
</Window>

在 main.cs 页面内，我加载了我将控制器的集合链接到 ScreenViewModel.Cells 属性，并加载了一些模板数据。只是非常基本的模拟数据（您还可以将屏幕模型附加到 DataContext 并在其他地方定义控制器，并更改 xaml 中的绑定以返回到 DataContext，但是通过资源，您还可以获取已经创建的实例（在 initializeComponent 之后）

protected ScreenViewModel ScreenViewModel
{
    get
    {
        return this.Resources["GridViewModel"] as ScreenViewModel;
    }
}

protected CellGridController Controller
{
    get
    {
        return this.Resources["CellController"] as CellGridController;
    }
}

protected void Load()
{
    var controller = Controller;
    controller.Collection.Clear();
    string[] rows = colorToCellSource.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
    string row;
    for (int x = 0; x < rows.Length; x++)
    {
        int length = rows[x].Length;
        ScreenViewModel.Rows = rows.Length;
        ScreenViewModel.Columns = length;
        row = rows[x];
        for (int y = 0; y < length; y++)
        {
            Cell cell = new Cell(x, y);
            cell.CellColor = row[y] == '0' ? Brushes.Transparent : Brushes.Blue;
            controller.Collection.Add(cell);
        }
    }
}

public MainWindow()
{
    InitializeComponent();
    if (Controller != null && ScreenViewModel != null)
    {
        ScreenViewModel.Cells = Controller.Collection;
        Load();
    }
}

屏幕重绘不到 1 秒，调整大小和最大化需要一点延迟，但我想这是可以预料的...（我的测试模板是 105x107）

Answer 2

听起来延迟是由解析模板和渲染如此多的项目引起的。

一些改进建议：

不要存储空单元格。仅存储其中包含 "data" 的单元格。
使用静态绑定 ItemTemplate 而不是动态解析类型
尝试简化您的 ItemTemplate

对于第一点，我会尝试在这里使用两层而不是一层：一层用于绘制网格，另一层位于其顶部以在网格中的特定位置绘制对象。

XAML 看起来像这样

<Grid>
    <UniformGrid Rows="{Binding RowCount}" Columns="{Binding ColumnCount}" />
    <ItemsControl ItemsSource="{Binding Cells}" .... />
</Grid>

其中 ItemsControl 使用 Canvas 作为 ItemContainerTemplate，并将 Canvas.Top 和 Canvas.Left 绑定到ItemContainerStyle，可能使用某种转换器将 X、Y 值乘以网格单元格大小。

要显示网格线，您可以使用 ShowGridLines=True 来获得模糊的虚线，或者使用像 this one 这样的自定义网格覆盖 OnRender 来绘制网格线.这也有助于减少第三点的 ItemTemplate 中的对象数量，因为您现在不需要 <Border> 对象。

我也不完全确定你想如何与你的网格交互，但将所有鼠标处理程序放在后台网格本身而不是每个单独的项目上可能有助于初始加载时间，并且简单通过 X,Y 位置计算鼠标下方的项目。为此，您可能必须确保在 ItemContainerStyle 中设置了 IsHitTestVisible="False"。

对于第二点（和），使用静态模板而不是基于对象类型的动态模板肯定会有帮助。

因此，不要使用隐式模板，而是给您的模板一个 x:Key 属性并使用静态绑定

绑定它

<DataTemplate x:Key="CellTemplate" DataType="{x:Type local:Cell}">
    <Border BorderBrush="Black" BorderThickness="0.1">
        <Grid Background="{Binding CellColor}">
            <i:Interaction.Triggers>
                <i:EventTrigger EventName="MouseMove" >
                    <ei:CallMethodAction TargetObject="{Binding}" MethodName="MouseHoveredOver"/>
                </i:EventTrigger>
            </i:Interaction.Triggers>
        </Grid>
    </Border>
</DataTemplate>

<ItemsControl ItemTemplate="{StaticResource CellTemplate}" ... />

为最短路径优化由 WPF 中的单元格组成的网格

Optimizing a Grid consisting of cells in WPF for Shortest Path

c#

wpf

xaml

shortest-path